Sharif Digital Repository

In this paper, we present a randomized LOCAL constant approximation factor algorithm for minimum dominating set (MDS) problem and minimum total dominating set (MTDS) problem in graphs. The approximation factor of this algorithm for planar graphs with no 4-cycles is 18 and 9 for MDS and MTDS problems, respectively. © 2020 Owner/Author  

For many years, computer designers benefitted from Moore's law and Dennard scaling to significantly improve the speed of single-core processors. The failure of Dennard scaling pushed the computer industry toward homogenous multicore processors for the performance improvement to continue without significant increase in power consumption. Unfortunately, even homogeneous multicore processors cannot offer the level of energy efficiency required to operate all the cores at the same time in today's and especially tomorrow's technologies. As a result of lack of energy efficiency, not all the cores in a multicore processor can be functional at the same time. This phenomenon is referred to as dark... 

Many applications, including big-data server applications, frequently encounter data misses. Consequently, they lose significant performance potential. Fortunately, data accesses of many of these applications follow temporal correlations, which means data accesses repeat over time. Temporal correlations occur because applications usually consist of loops, and hence, the sequence of instructions that constitute the body of a loop repeats many times, leading to data access repetition. Temporal data prefetchers take advantage of temporal correlation to predict and prefetch future memory accesses. In this chapter, we introduce the concept of temporal prefetching and present two instances of... 

Many applications extensively use data objects with a regular and fixed layout, which leads to the recurrence of access patterns over memory regions. Spatial data prefetching techniques exploit this phenomenon to prefetch future memory references and hide their long latency. Spatial prefetchers are particularly of interest because they usually only need a small storage budget. In this chapter, we introduce the concept of spatial prefetching and present two instances of spatial data prefetchers, SMS and VLDP. © 2021 Elsevier Inc  

Many applications, including big-data server applications, frequently encounter data misses. Consequently, they lose significant performance potential. Fortunately, data accesses of many of these applications follow temporal correlations, which means data accesses repeat over time. Temporal correlations occur because applications usually consist of loops, and hence, the sequence of instructions that constitute the body of a loop repeats many times, leading to data access repetition. Temporal data prefetchers take advantage of temporal correlation to predict and prefetch future memory accesses. In this chapter, we introduce the concept of temporal prefetching and present two instances of... 

Many applications extensively use data objects with a regular and fixed layout, which leads to the recurrence of access patterns over memory regions. Spatial data prefetching techniques exploit this phenomenon to prefetch future memory references and hide their long latency. Spatial prefetchers are particularly of interest because they usually only need a small storage budget. In this chapter, we introduce the concept of spatial prefetching and present two instances of spatial data prefetchers, SMS and VLDP. © 2022 Elsevier Inc  

For a set of n disjoint line segments S in R2, the visibility counting problem (VCP) is to preprocess S such that the number of visible segments in S from a query point p can be computed quickly. For this configuration, the visibility testing problem (VTP) is to test whether p sees a fixed segment s. These problems can be solved in logarithmic query time by using O(n4) preprocessing time and space. In this paper, we approximately solve this problem using quadratic preprocessing time and space. Our methods are superior to current approximation algorithms in terms of both approximation factor and preprocessing cost. In this paper, we propose a 2-approximation algorithm for the VCP using at... 

In real applications, there are situations where we need to model some problems based on uncertain data. This leads us to define an uncertain model for some classical geometric optimization problems and propose algorithms to solve them. The assigned version of the k-center problem for n uncertain points in a metric space is studied in this paper. The main approach is to replace each uncertain point with a clever choice of a certain point. We argue that the k-center solution for these certain replacements of our uncertain points, is a good constant approximation factor for the original uncertain k-center problem. This approach enables us to present fast and simple algorithms that give... 

In this study, elastic energy trapping strategy is exploited to investigate the energy absorption capability of origami structures. The twofold novelty of this paper can be summarized as (i) comprehensive analysis of a single Kresling module from a geometrical point of view to illustrate its energy trapping capability in the pathway of compression; (ii) introducing translational and torsional ACKS (achiral coupled Kresling structures); demonstrating their potential to be utilized as a platform for designing energy absorption systems that can trap energy applied by compressional and torsional loads. The outcomes pave the way toward utilizing origami structures in reusable energy-absorbing... 

Knowing the exact position and rotation is a crucial necessity for the navigation of autonomous robots. Even in outdoor environments GPS signals are not always accessible for estimating online rotation and position of robots. Also inertial aided navigation methods have their own defects such as the drift of gyroscope or inaccuracy of accelerometer in agile motions and environmental sensitivity of compass. In this article, we have introduced a novel online visual gyroscope that can estimate the rotation of a moving car with analyzing the images of a monocular camera installed on it. Our real time visual gyroscope utilizes an efficient method of rotation estimation between each pair of camera... 

Side Channel Analysis (SCA) are still harmful threats against security of embedded systems. Due to the fact that every kind of SCA attack or countermeasure against it needs to be implemented before evaluation, a huge amount of time and cost of this process is paid for providing high resolution measurement tools, calibrating them and also implementation of proposed design on ASIC or target platform. In this paper, we have introduced a novel simulation platform for evaluation of power based SCA attacks and countermeasures. We have used Synopsys power analysis tools in order to simulate a processor and implement a successful Differential Power Analysis (DPA) attack on it. Then we focused on the... 

Chip multiprocessors (CMPs) require a low-latency interconnect fabric network-on-chip (NoC) to minimize processor stall time on instruction and data accesses that are serviced by the last-level cache (LLC). While packet-switched mesh interconnects sacrifice performance of many-core processors due to NoC-induced delays, existing circuit-switched interconnects do not offer lower network delays as they cannot hide the time it takes to set up a circuit. To address this problem, this work introduces CIMA - a hybrid circuit-switched and packet-switched mesh-based interconnection network that affords low LLC access delays at a small area cost. CIMA uses virtual cut-through (VCT) switching for short... 

Server workloads benefit from execution on many-core processors due to their massive request-level parallelism. A key characteristic of server workloads is the large instruction footprints. While a shared last-level cache (LLC) captures the footprints, it necessitates a low-latency network-on-chip (NOC) to minimize the core stall time on accesses serviced by the LLC. As strict quality-of-service requirements preclude the use of lean cores in server processors, we observe that even state-of-the-art single-cycle multi-hop NOCs are far from ideal because they impose significant NOC-induced delays on the LLC access latency, and diminish performance. Most of the NOC delay is due to per-hop...