6205132
Improving Data Locality by Array Contraction
Array contraction is a program transformation which reduces array size while preserving the correct output. In this paper, we present an aggressive array-contraction technique and study its impact on memory system performance. This technique, called controlled SFC, combines loop shifting and controlled loop fusion to maximize opportunities for array contraction within a given loop nesting. A controlled fusion scheme is used to prevent overfusing loops and to avoid excessive pressure on the cache and the registers. Reducing the array size increases data reuse because of the increased average number of memory operations on the same memory addresses. Furthermore, if the data size of a loop nest fits in the cache after array contraction, then repeated references to the same variable in the loop nest generate cache hits, assuming set conflicts are eliminated successfully.
20563509
A theoretical foundation for program transformations to reduce cache thrashing due to true data sharing
Cache thrashing due to true data sharing can degrade the performance of parallel programs significantly. Our previous work showed that parallel task alignment via program transformations can be quite effective for the reduction of such cache thrashing. In this paper, we present a theoretical foundation for such program transformations. Based on linear algebra and the theory of numbers, our work analyzes the data dependences among the tasks created by a fork-join parallel program and determines at compile time how these tasks should be assigned to processors in order to reduce cache thrashing due to true data sharing. Our analysis and program transformations can be easily performed by compilers for parallel computers.
12116647
Data locality enhancement by memory reduction
In this paper, we propose memory reduction as a new approach to data locality enhancement. Under this approach, we use the compiler to reduce the size of the data repeatedly referenced in a collection of nested loops. Between their reuses, the data will more likely remain in higher-speed memory devices, such as the cache. Specifically, we present an optimal algorithm to combine loop shifting, loop fusion and array contraction to reduce the temporary array storage required to execute a collection of loops. When applied to 20 benchmark programs, our technique reduces the memory requirement, counting both the data and the code, by 51% on average. The transformed programs gain a speedup of 1.40 on average, due to the reduced footprint and, consequently, the improved data locality.
31492830
On Reducing Data Synchronization in Multiprocessed Loops
In this correspondence we present and prove the correctness of an algorithm for reducing the number of synchronized memory references to shared data elements in multiprocessed loops. Optimizing compilers for shared memory multiprocessors can use this algorithm to reduce synchronization overhead. The algorithm has been implemented as a new module in the multiprocessors version of Parafrase, the restructuring system of the University of Illinois. We present a brief discussion of experiments we performed to asses the effectiveness of this algorithm in reducing the synchronization overhead for the 61 subroutines of EISPACK, a package for computing matrix eigenvectors and eigenvalues.
14156120
A compiler scheme for reusing intermediate computation results
Recent research has shown that programs often exhibit value locality. Such locality occurs when a code segment, although executed repeatedly in the program, takes only a small number of different values as input and, naturally, generates a small number of different outputs. It is potentially beneficial to replace such a code segment by a table, which records the computation results for the previous inputs. When the program execution re-enters the code segment with a repeated input, its computation can be simplified to a table look-up. We discuss a compiler scheme to identify code segments, which are good candidates for computation reuse. We discuss the conditions under which the table look-up costs less than repeating the execution, and we perform profiling to identify candidates, which have many repeated inputs at run time. Compared to previous work, this scheme requires no special hardware support and is therefore particularly useful for resource constrained systems such as handheld computing devices. We implement our scheme and its supporting analyses in GCC. We experiment with several multimedia benchmarks and the GNU Go game by executing them on a handheld computing device. The results show the scheme to improve the performance and to reduce the energy consumption quite substantially for these programs.
37872646
The Cedar System And An Initial Performance Study
In this paper, we give an overview of the Cedar mutliprocessor and present recent performance results. These include the performance of some computational kernels and the Perfect Benchmarks@ . We also present a methodology f o r judging parallel system performance and apply this methodology to Cedar, Cray YMP-8, and Thinking Machines CM-5.
14458845
QoS-aware multicasting in DiffServ domains
QoS-aware multicasting is becoming more and more desirable with the expanding usage of group-based applications, especially those involving multimedia objects. Until now, most of the proposed QoS-aware multicasting routing protocols adopt per-flow based resource reservation. Although these schemes can be adopted in integrated services (IntServ) Internet, they are not suitable for more scalable Differentiated Services (DiffServ) Internet. A new QoS-aware multicast routing protocol called QMD is proposed for DiffServ environments in this paper. Based on the design philosophy of DiffServ, the complex multicasting control plane functionalities are removed from the core routers. In addition, for each multicast group, only a limited set of on-tree routers (termed as key nodes) maintain multicast routing states and forward multicast data traffic. The key nodes of a multicast group uniquely identify a QoS-satisfied multicast tree connecting the group members. Although the other on-tree routers between any two key nodes do not maintain any multicast routing states and QoS reservation information, the group members' QoS requirements can still be satisfied. Through simulation experiments based on both random and real intra-domain topologies, we have also demonstrated that QMD can provide higher QoS-satisfaction rate while maintaining the simplicity of core routers.
12665870
Robust statistical methods for securing wireless localization in sensor networks
Many sensor applications are being developed that require the location of wireless devices, and localization schemes have been developed to meet this need. However, as location-based services become more prevalent, the localization infrastructure will become the target of malicious attacks. These attacks will not be conventional security threats, but rather threats that adversely affect the ability of localization schemes to provide trustworthy location information. This paper identifies a list of attacks that are unique to localization algorithms. Since these attacks are diverse in nature, and there may be many unforeseen attacks that can bypass traditional security countermeasures, it is desirable to alter the underlying localization algorithms to be robust to intentionally corrupted measurements. In this paper, we develop robust statistical methods to make localization attack-tolerant. We examine two broad classes of localization: triangulation and RF-based fingerprinting methods. For triangulation-based localization, we propose an adaptive least squares and least median squares position estimator that has the computational advantages of least squares in the absence of attacks and is capable of switching to a robust mode when being attacked. We introduce robustness to fingerprinting localization through the use of a median-based distance metric. Finally, we evaluate our robust localization schemes under different threat conditions.
14010825
C-Miner: Mining Block Correlations in Storage Systems
Block correlations are common semantic patterns in storage systems. These correlations can be exploited for improving the effectiveness of storage caching, prefetching, data layout and disk scheduling. Unfortunately, information about block correlations is not available at the storage system level. Previous approaches for discovering file correlations in file systems do not scale well enough to be used for discovering block correlations in storage systems. 
 
In this paper, we propose C-Miner, an algorithm which uses a data mining technique called frequent sequence mining to discover block correlations in storage systems. C-Miner runs reasonably fast with feasible space requirement, indicating that it is a practical tool for dynamically inferring correlations in a storage system. Moreover, we have also evaluated the benefits of block correlation-directed prefetching and data layout through experiments. Our results using real system workloads show that correlation-directed prefetching and data layout can reduce average I/O response time by 12-25% compared to the base case, and 7-20% compared to the commonly used sequential prefetching scheme.
566308
Reducing Energy Consumption of Disk Storage Using Power-Aware Cache Management
Reducing energy consumption is an important issue for data centers. Among the various components of a data center, storage is one of the biggest consumers of energy. Previous studies have shown that the average idle period for a server disk in a data center is very small compared to the time taken to spin down and spin up. This significantly limits the effectiveness of disk power management schemes. This paper proposes several power-aware storage cache management algorithms that provide more opportunities for the underlying disk power management schemes to save energy. More specifically, we present an off-line power-aware greedy algorithm that is more energy-efficient than Belady’s off-line algorithm (which minimizes cache misses only). We also propose an online power-aware cache replacement algorithm. Our trace-driven simulations show that, compared to LRU, our algorithm saves 16% more disk energy and provides 50% better average response time for OLTP I/O workloads. We have also investigated the effects of four storage cache write policies on disk energy consumption.
130258
Longest-path selection for delay test under process variation
Under manufacturing process variation, a path through a fault site is called longest for delay test if there exists a process condition under which the path has the maximum delay among all paths through that fault site. There are often multiple longest paths for each fault site in the circuit, due to different process conditions. To detect the smallest delay fault, it is necessary to test all longest paths through the fault site. However, previous methods are either inefficient or their results include too many paths that are not longest.This paper presents an efficient method to generate the longest path set for delay test under process variation. To capture both structural and systematic process correlation, we use linear delay functions to express path delays under process variation. A novel path-pruning technique is proposed to discard paths that are not longest, resulting in a significantly reduction in the number of paths compared with the previous best method. The new method can be applied to any process variation as long as its impact on delay is linear.