Estimating and reducing the memory requirements of signal processing codes for embedded systems

Most embedded systems have limited amount of memory. In contrast, the memory requirements of the digital signal processing (DSP) and video processing codes (in nested loops, in particular) running on embedded systems is significant. This paper addresses the problem of estimating and reducing the amount of memory needed for transfers of data in embedded systems. First, the problem of estimating the region associated with a statement or the set of elements referenced by a statement during the execution of nested loops is analyzed. For a fixed execution ordering, a quantitative analysis of the number of elements referenced is presented; exact expressions for uniformly generated references and a close upper and lower bound for nonuniformly generated references are derived. Second, in addition to presenting an algorithm that computes the total memory required, this paper also discusses the effect of transformations (that change the execution ordering) on the lifetimes of array variables, i.e., the time between the first and last accesses to a given array location. The term maximum window size is introduced, and quantitative expressions are derived to compute the maximum window size. A detailed analysis of the effect of unimodular transformations on data locality, including the calculation of the maximum window size, is presented.     

Adapting application execution in CMPs using helper threads

In parallel to the changes in both the architecture domain–the move toward chip multiprocessors (CMPs)–and the application domain–the move toward increasingly data-intensive workloads–issues such as performance, energy efficiency and CPU availability are becoming increasingly critical. The CPU availability can change dynamically due to several reasons such as thermal overload, increase in transient errors, or operating system scheduling. An important question in this context is how to adapt, in a CMP, the execution of a given application to CPU availability change at runtime. Our paper studies this problem, targeting the energy-delay product (EDP) as the main metric to optimize. We first discuss that, in adapting the application execution to the varying CPU availability, one needs to consider the number of CPUs to use, the number of application threads to accommodate and the voltage/frequency levels to employ (if the CMP has this capability). We then propose to use helper threads to adapt the application execution to CPU availability change in general with the goal of minimizing the EDP. The helper thread runs parallel to the application execution threads and tries to determine the ideal number of CPUs, threads and voltage/frequency levels to employ at any given point in execution. We illustrate this idea using four applications (Fast Fourier Transform, MultiGrid, LU decomposition and Conjugate Gradient) under different execution scenarios. The results collected through our experiments are very promising and indicate that significant EDP reductions are possible using helper threads. For example, we achieved up to 66.3%, 83.3%, 91.2%, and 94.2% savings in EDP when adjusting all the parameters properly in applications FFT, MG, LU, and CG, respectively. We also discuss how our approach can be extended to address multi-programmed workloads.     

Compiler-Directed Code Restructuring for Improving Performance of MPSoCs

One of the critical goals in code optimization for multi-processor-system-on-a-chip (MPSoC) architectures is to minimize the number of off-chip memory accesses. This is because such accesses can be extremely costly from both performance and power angles. While conventional data locality optimization techniques can be used for improving data access pattern of each processor independently, such techniques usually do not consider locality for shared data. This paper proposes a strategy that reduces the number of off-chip references due to shared data. It achieves this goal by restructuring a parallelized application code in such a fashion that a given data block is accessed by parallel processors within the same time frame, so that its reuse is maximized while it is in the on-chip memory space. This tends to minimize the number of off-chip references since the accesses to a given data block are clustered within a short period of time during execution. Our approach employs a polyhedral tool that helps us isolate computations that manipulate a given data block. In order to test the effectiveness of our approach, we implemented it using a publicly-available compiler infrastructure and conducted experiments with twelve data-intensive embedded applications. Our results show that optimizing data locality for shared data elements is very useful in practice.     

Thread vulnerability in parallel applications

Continuously reducing transistor sizes and aggressive low power operating modes employed by modern architectures tend to increase transient error rates. Concurrently, multicore machines are dominating the architectural spectrum today in various application domains. These two trends require a fresh look at resiliency of multithreaded applications against transient errors from a software perspective. In this paper, we propose and evaluate a new metric called the Thread Vulnerability Factor (TVF$TVF$). A distinguishing characteristic of TVF$TVF$ is that its calculation for a given thread (which is typically one of the threads of a multithreaded application) does not depend on its code alone, but also on the codes of the threads that share resources and data with that thread. As a result, we decompose TVF$TVF$ of a thread into two complementary parts: local and remote. While the former captures the TVF$TVF$ induced by the code of the target thread, the latter represents the vulnerability impact of the threads that interact with the target thread. We quantify the local and remote TVF$TVF$ values for three architectural components (register file, ALUs, and caches) using a set of ten multithreaded applications from the Parsec and Splash-2 benchmark suites. Our experimental evaluation shows that TVF$TVF$ values tend to increase as the number of cores increases, which means the system becomes more vulnerable as the core count rises. We further discuss how TVF$TVF$ metric can be employed to explore performance–reliability tradeoffs in multicores. Reliability-based analysis of compiler optimizations and redundancy-based fault tolerance are also mentioned as potential usages of our TVF$TVF$ metric.     

Assessment of coal deposit using multivariate statistical analysis techniques

Energy is one of the indispensable factors regarding the economic development of Turkey. Examination of calorific values in coal deposits has importance in the production of energy, and thus planning of the coal deposit. In this article, multivariate statistical analysis techniques, including cluster analysis and discriminant analysis, were applied to calorific values obtained from boreholes. Cluster analysis grouped borehole locations into two clusters based on the similarity of calorific values. Afterwards, discriminant functions were supported to cluster analysis and developed a linear discriminant function. Based on the locations of the boreholes, it was concluded that calorific values are a highly central part of the coal deposit. Thus, this article shows the usefulness of multivariate statistical analysis techniques for understanding spatial variation of coal deposits and effective deposit management.     

Molecular dynamics simulation of compressible hot/cold moving lid-driven microcavity flow

Hard-sphere molecular dynamics simulations of lid-driven microcavity gas flow with various subsonic speeds and lid temperatures are conducted. Simulations with faster and colder lids show streamlines of stronger primary vortices. Variations of mass and energy centers with respect to lid speed and temperature are examined. Center of energy is less sensitive to employed lid conditions than center of gravity is. Although moving lid imparts energy into fluid, due to change of impingement rates on the walls of fixed temperature, average energy within the cavity seems quite insensitive to the subsonic lid speed. Behavior of compressibility at both top corners is observed even at low Mach numbers widely considered within incompressible flow region. While high Knudsen number causes considerable property slips near the lid, two-dimensional pressure, density, and temperature plots of excellent quality are generated. Results are promising in use of molecular dynamics simulations for compressible vortex flow analyses while providing insights for understanding microfluidics and nanofluidics in context of molecular mass, momentum and heat transfer in microscale and nanoscale systems.     

An experimental evaluation of I/O optimizations on different applications

Many large scale applications have significant I/O requirements as well as computational and memory requirements. Unfortunately, the limited number of I/O nodes provided in a typical configuration of the modern message-passing distributed-memory architectures such as Intel Paragon and IBM SP-2 limits the I/O performance of these applications severely. We examine some software optimization techniques and evaluate their effects in five different I/O-intensive codes from both small and large application domains. Our goals in this study are twofold. First, we want to understand the behavior of large-scale data-intensive applications and the impact of I/O subsystems on their performance and vice versa. Second, and more importantly, we strive to determine the solutions for improving the applications' performance by a mix of software techniques. Our results reveal that different applications can benefit from different optimizations. For example, we found that some applications benefit from file layout optimizations whereas others take advantage of collective I/O. A combination of architectural and software solutions is normally needed to obtain good I/O performance. For example, we show that with a limited number of I/O resources, it is possible to obtain good performance by using appropriate software optimizations. We also show that beyond a certain level, imbalance in the architecture results in performance degradation even when using optimized software, thereby indicating the necessity of an increase in I/O resources.     

Optimizing Leakage Energy Consumption in Cache Bitlines

As technology scales down into deep-submicron, leakage energy is becoming a dominant source of energy consumption. Leakage energy is generally proportional to the area of a circuit and caches constitute a large portion of the die area. Therefore, there has been much effort to reduce leakage energy in caches. Most techniques have been targeted at cell leakage energy optimization. Bitline leakage energy is critical as well. To this end, we propose a predictive precharging scheme to reduce bitline leakage energy consumption. Results show that energy savings are significant with little performance degradation. Also, our predictive precharging is more beneficial in more aggressively scaled technologies.     

Influence of compiler optimizations on system power

Optimizing for energy constraints is of critical importance due to the proliferation of battery-operated embedded devices. Thus, it is important to explore both hardware and software solutions for optimizing energy. The focus of high-level compiler optimizations has traditionally been on improving performance. In this paper, we present an experimental evaluation of several state-of-the-art high-level compiler optimizations on energy consumption, considering both the processor core (datapath) and memory system. This is in contrast to many of the previous works that have considered them in isolation