Dynamic task-parallel programming models are popular on shared-memory systems, promising enhanced scalability, load balancing and locality. Yet these promises are undermined by non-uniform memory access (NUMA). We show that using NUMA-aware task and data placement, it is possible to preserve the uniform abstraction of both computing and memory resources for task-parallel programming models while achieving high data locality. Our data placement scheme guarantees that all accesses to task output data target the local memory of the accessing core. The complementary task placement heuristic improves the locality of task input data on a best effort basis. Our algorithms take advantage of data-flow style task parallelism, where the privatization of task data enhances scalability by eliminating false dependences and enabling fine-grained dynamic control over data placement. The algorithms are fully automatic, application-independent, performance-portable across NUMA machines, and adapt to dynamic changes. Placement decisions use information about inter-task data dependences readily available in the run-time system and placement information from the operating system. We achieve 94% of local memory accesses on a 192-core system with 24 NUMA nodes, up to 5x higher performance than NUMA-aware hierarchical work-stealing, and even 5.6x compared to static interleaved allocation. Finally, we show that state-of-the-art dynamic page migration by the operating system cannot catch up with frequent affinity changes between cores and data and thus fails to accelerate task-parallel applications.

Dynamic task parallelism is a popular programming model on shared-memory systems. Compared to data parallel loop-based concurrency, it promises enhanced scalability, load balancing and locality. These promises, however, are undermined by non-uniform memory access (NUMA) systems. We show that it is possible to preserve the uniform hardware abstraction of contemporary task-parallel programming models, for both computing and memory resources, while achieving near-optimal data locality. Our run-time algorithms for NUMA-aware task and data placement are fully automatic, application-independent, performance-portable across NUMA machines, and adapt to dynamic changes. Placement decisions use information about inter-task data dependences and reuse. This information is readily available in the run-time systems of modern task-parallel programming frameworks, and from the operating system regarding the placement of previously allocated memory. Our algorithms take advantage of data-flow style task parallelism, where the privatization of task data enhances scalability through the elimination of false dependences and enables fine-grained dynamic control over the placement of application data. We demonstrate that the benefits of dynamically managing data placement outweigh the privatization cost, even when comparing with target-specific optimizations through static, NUMA-aware data interleaving. Our implementation and the experimental evaluation on a set of high-performance benchmarks executing on a 192-core system with 24 NUMA nodes show that the fraction of local memory accesses can be increased to more than 99%, resulting in a speedup of up to 5× compared to a NUMA-aware hierarchical work-stealing baseline.

We present a joint scheduling and memory allocation algorithm for efficient execution of task-parallel programs on non-uniform memory architecture (NUMA) systems. Task and data placement decisions are based on a static description of the memory hierarchy and on runtime information about intertask communication. Existing locality-aware scheduling strategies for fine-grained tasks have strong limitations: they are specific to some class of machines or applications, they do not handle task dependences, they require manual program annotations, or they rely on fragile profiling schemes. By contrast, our solution makes no assumption on the structure of programs or on the layout of data in memory. Experimental results, based on the OpenStream language, show that locality of accesses to main memory of scientific applications can be increased significantly on a 64-core machine, resulting in a speedup of up to 1.63× compared to a state-of-the-art work-stealing scheduler.

Embedded systems based on FPGA (Field-Programmable Gate Arrays) must exhibit more performance for new applications. However, no high-performance superscalar soft processor is available on the FPGA, because the superscalar architecture is not suitable for FPGAs. High-performance superscalar processors execute instructions out-of-order and it is necessary to re-order instructions after execution. This task is performed by the ROB (ReOrder Buffer) that uses usually multi-ports RAM, but only two-port buffers are available in FPGA. In this work, we propose a FPGA friendly ROB (ReOrder Buffer) architecture using only 2 ports RAM called a multi-bank ROB architecture. The ROB is the main and more complex structure in an out-of-order superscalar processor. Depending on processor architecture parameters, the FPGA implementation of our ROB compared to a classic architecture, requires 5 to 7 times less registers, 1.5 to 8.3 times less logic gates and 2.6 to 32 times less RAM blocks.

For security issues in portable applications such as smart card, various proposed techniques can be applied to harden the ALU against fault attacks. Among others, time redundancy is a good candidate to offer a low hardware cost. The main disadvantage of this scheme is high extra time due to the recomputation. However, this impact can be considerably reduced by exploiting idle hardware in the ALU. In this paper, we will show that applying this scheme in a simple processor-based smart card can reduce down to 30%-20% of extra time and requires a reasonable hardware overhead about 20.4%.

Increasingly complex consumer electronics applications call for embedded processors with higher performance. Multi-cores are capable of delivering the required performance. However, many of these embedded applications must meet some form of soft real-time constraints, and program behavior on multi-cores is even harder to predict than on single-cores. In this article, we highlight the greater performance variability of irregular applications (non-regular control flow and/or data structures) across data sets when parallelized and run on a multi-core. We then show that a proper parallelization approach coupled with a lightweight run-time system can drastically reduce this performance variability without sacrificing their performance. This approach requires no complex program or architecture analysis or modeling. Moreover, we show that parallel program performance becomes stable enough that it is possible to reasonably and accurately predict it by sampling a few training runs.

To meet the high demand for powerful embedded processors, VLIW architectures are increasingly complex (e.g., multiple clusters), and moreover, they now run increasingly sophisticated control-intensive applications. As a result, developing architecture-specific compiler optimizations is becoming both increasingly critical and complex, while time-to-market constraints remain very tight. We present a novel program optimization approach, called the virtual hardware compiler (VHC), that can perform as well as static compiler optimizations, but which requires far less compiler development effort, even for complex VLIW architectures and complex target applications. The principle is to augment the target processor simulator with superscalar-like features, observe how the target program is dynamically optimized during execution, and deduce an optimized binary for the static VLIW architecture. Developing an architecture-specific optimizer then amounts to modifying the processor simulator which is very fast compared to adapting static compiler optimizations to an architecture. We also show that a VHC-optimized binary trained on a number of data sets performs as well as a statically-optimized binary on other test data sets. The only drawback of the approach is a largely increased compilation time, which is often acceptable for embedded applications and devices. Using the Texas Instruments C62 VLIW processor and the associated compiler, we experimentally show that this approach performs as well as static compiler optimizations for a much lower research and development effort. Using a single-core C60 and a dual-core clustered C62 processors, we also show that the same approach can be used for efficiently retargeting binary programs within a family of processors.

In this paper we evaluate the performance of an SMT processor used as the geometry processor for a 3D polygonal rendering engine. To evaluate this approach, we consider PMesa (a parallel version of Mesa) which parallelizes the geometry stage of the 3D pipeline. We show that SMT is suitable for 3D geometry and we characterize the execution of the geometry stage in term of memory hierarchy, which is the main bottleneck. The results show that latency is not fully recovered by SMT; the use of L2 data prefetching does not succeed in increasing the performance. We show that this problem comes from a pollution of the instruction window by the threads experiencing L2 cache misses, thus reducing the window available for the other threads. We thus propose dcPRED, a hardware mechanism to predict L2 misses and control this pollution. Coupled with L2 data prefetching, dcPRED achieves gains up to 21% over the baseline SMT.

The quality of a real-time high-end virtual reality system depends on its ability to draw millions of textured triangles in 1/60 s. The idea of using commodity PC 3D accelerators to build a parallel machine instead of custom ASICs seems more and more attractive as such chips are getting faster. If image parallelism is used, designers have the choice between two distributions: line interleaving and square block interleaving. Having a fixed block shape and size makes chip design easier. A PC 3D accelerator has a cost-effective external bus and an on-chip texture cache. The performance of such a cache depends on spatial locality. If the image is rendered on multiple engines, this locality is reduced. Locality and load balancing depend on the distribution scheme of the machine. This paper investigates the impact of the distribution scheme on the performance of such a machine. We use detailed cache and memory system simulations with virtual reality benchmarks running on different configurations. We show that: (i) both distributions have the same maximum performance with less than 16 processors, but the square block has a better speedup with 64 processors; (ii) the best SLI (scan-line interleaving) block size depends on the number of processors of the machine and is not suitable for a scalable chip with a fixed block size; and (iii) using a large triangle buffer in the texture mapping engine has a very important impact on the performance.

As technology enables to integrate real-time good quality 30 rendering in a single chip, the classicalproblem of the gap between internal data bandwidth and external memories arisea.The texture mapping function requires a twmendous number of texture accesses and many past implementations have been based on costly high bandwidth external memory.OUT impact study of texture cache used with today's commercial representative 30 software shows that it is possible to render 100 million pixels per second while using an internal cache smaller than 32 KB and a PC memory bus for textures.Texture blocking and number of requests on the cache contribute mainly to those Tesults.Building a high performance parallel subsystem based on such a chip may become an interesting opportunityfor 1eadingpeTformance3D graphic manufacturers though many problems have been observed with caches in parallel machines.As far as texture accesses are concerned, we show that image parallelism generates poor performance with caches.But triangle parallelism scales with multiple rendering processors, each having its own texture cache and the speedup is nearly linear.'A texrl is a pixel in the texture map

Hardware and software cache optimizations are active fields of research, that have yielded powerful but occasionally complex designs and algorithms. The purpose of this paper is to investigate the performance of combined though simple software and hardware optimizations. Because current caches provide little flexibility for exploiting temporal and spatial locality, two hardware modifications are proposed to support these two kinds of locality. Spatial locality is exploited by using large virtual cache lines which do not exhibit the performance flaws of large physical cache lines. Temporal locality is exploited by minimizing cache pollution with a bypass mechanism that still allows to exploit spatial locality. Subsequently, it is shown that simple software informations on the spatial/temporal locality of array references, as provided by current data locality optimizing algorithms, can be used to significantly increase cache performance. The performance and design trade-offs of the proposed mechanisms are discussed. Software assisted caches are further shown to provide a convenient support for hardware and software optimizations.>

Article Hardware implementation issues of data prefetching Share on Author: Nathalie Drach Laboratoire de Recherche en Informatique, Université de Paris XI, 91405 Orsay Cedex, France Laboratoire de Recherche en Informatique, Université de Paris XI, 91405 Orsay Cedex, FranceView Profile Authors Info & Claims ICS '95: Proceedings of the 9th international conference on SupercomputingJuly 1995 Pages 245–254https://doi.org/10.1145/224538.224568Published:03 July 1995 10citation256DownloadsMetricsTotal Citations10Total Downloads256Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The purpose of the semi-unified on-chip cache organization, is to use the data cache (resp. ins truction cache) as an on-chip second-level cache for instructions (resp. data). Thus the associativity de gree of both on-chip caches is artificially increased, and the cache spaces respectively devoted to instruc tions and data are dynamically adjusted. The off-chip miss ratio of a semi-unified cache built with two directmapped caches of size S is equal to the miss ratio of a unified two-way set associative cache of size 2S; yet, the hit time of this semi-unified cache is equal to the hit time of a direct-mapped cache. Trace driven simu lations show that using a direct-mapped semi-unified cache organization leads to higher overall system per formance than using usual split instruction/data cache organization.

Speculative execution and dynamic scheduling are two promising techniques for achieving high performance in superscalar processors. These techniques require a mechanism for maintaining all architecturally visible machine state. The authors examine the performance implications of three common state maintenance mechanisms: the reorder buffer, the history buffer, and checkpointing. They model the execution of the four integer benchmarks from the SPEC89 suite for a variety of maintenance techniques. They report the results of these measurements and their implications with respect to the design of high performance superscalar processors.>