We present an enterprise-level Internet video cache and streaming system that generalizes “cache hits” to videos that are at least similar, human perception-wise. When a user requests a video not in our cache, our system starts streaming the video from the Internet, and forwards it to the user. We efficiently extract feature vectors from the incoming byte stream, comparing them to feature vectors of cached videos, all in real time. After a short period, we may decide that we have a similar video (but that is not byte-wise identical). We then stop the Internet-side download, and continue streaming to the user using the similar video instead, saving valuable resources. Our system makes similarity decisions with rates of incorrectness approaching zero, after only 30 seconds of Internet-side streaming.

Parallel loops, such as a parallel DO loop, in Fortran, account for large percentage of the total execution time. Given this, we focus on the problem of how to efficiently schedule nested perfect/non-perfect parallel loops on the emerging multi-core systems. In this regard, one of the key aspects is how to determine the profitability of parallel execution and how to efficiently capture the cache behavior as the cache subsystem is often the main performance bottleneck in multi-core systems. In this paper, we present a novel profile-guided compiler technique for cache-aware scheduling of iteration spaces of such loops. Specifically, we propose a technique for iteration space scheduling which captures the effect of variation in the number of cache misses across the iteration space. Subsequently, we propose a general approach to capture the variation of both the number of cache misses and computation across the iteration space. We demonstrate the efficacy of our approach on a dedicated 4-way Intel®Xeon®based multiprocessor using several kernels from the industry-standard benchmarks.

The need for high performance per watt has led to development of multi-core systems such as the Intel Core 2 Duo processor and the Intel quad-core Kentsfield processor. Maximal exploitation of the hardware parallelism supported by such systems necessitates the development of concurrent software. This, in part, entails automatic parallelization of programs and efficient mapping of the parallelized program onto the different cores. The latter affects the load balance between the different cores which in turn has a direct impact on performance. In light of the fact that, parallel loops, such as a parallel DO loop in Fortran, account for a large percentage of the total execution time, we focus on the problem of how to efficiently partition the iteration space of (possibly) nested perfect/non-perfect parallel loops. In this regard, one of the key aspects is how to efficiently capture the cache behavior as the cache subsystem is often the main performance bottleneck in multi-core systems. In this paper, we present a novel profile-guided compiler technique for cache-aware scheduling of iteration spaces of such loops. Specifically, we propose a technique for iteration space scheduling which captures the effect of variation in the number of cache misses across the iteration space. Subsequently, we propose a general approach to capture the variation of both the number of cache misses and computation across the iteration space. We demonstrate the efficacy of our approach on a dedicated 4-way Intel® Xeon® based multiprocessor using several kernels from the industry-standard SPEC CPU2000 and CPU2006 benchmarks achieving speedups upto 62.5%.

The need for high performance per watt has led to the development of multi-core systems such as the Intel Core 2 Duo processor and the Intel quad-core Kentsfield processor. Maximal exploitation of the hardware parallelism supported by such systems necessitates the development of concurrent software. This, in part, entails program parallelization and efficient mapping of the parallelized program onto the different cores. The latter affects the load balance between the different cores which in turn has a direct impact on performance. In light of the fact that parallel loops, such as a parallel DO loop in Fortran, account for a large percentage of the total execution time, we focus on the problem of how to efficiently partition the iteration space of (possibly) nested perfect/non-perfect parallel loops. In this regard, one of the key aspects is how to efficiently capture the cache behavior as the cache subsystem is often the main performance bottleneck in multi-core systems. In this paper, we present a novel profile-guided compiler technique for cache-aware partitioning of iteration spaces of parallel loops. We present a case study using a kernel from the industry-standard SPEC CPU benchmark suite.

Multi-cores such as the Intel®1 Core™2 Duo processor, facilitate efficient thread-level parallel execution of ordinary programs, wherein the different threads-of-execution are mapped onto different physical processors. In this context, several techniques have been proposed for auto-parallelization of programs. Recently, thread-level speculation (TLS) has been proposed as a means to parallelize difficult-to-analyze serial codes. In general, more than one technique can be employed for parallelizing a given program. The overlapping nature of the applicability of the various techniques makes it hard to assess the intrinsic performance potential of each. In this paper, we present a tight analysis of the (unique) performance potential of both: (a) TLS in general and (b) specific types of thread-level speculation, viz., control speculation, data dependence speculation and data value speculation, for the SPEC2 CPU2006 benchmark suite in light of the various limiting factors such as the threading overhead and misspeculation penalty. To the best of our knowledge, this is the first evaluation of TLS based on SPEC CPU2006 and accounts for the aforementioned real-life con-straints. Our analysis shows that, at the innermost loop level, the upper bound on the speedup uniquely achievable via TLS with the state-of-the-art thread implementations for both SPEC CINT2006 and CFP2006 is of the order of 1%.

This paper analyzes the session setup delay in the IP multimedia subsystem (IMS) with the CDMA2000 evolution data only rev. A (EV-DO rev. A) standard for wireless transmission. Session setup delay is particularly critical for interactive multimedia applications, such as gaming, push-to-X and voice over IP (VoIP), as it directly translates in user perception of service quality. Keeping signaling delay low, however, is a challenge in IMS due to the text-based nature of the session initiation protocol (SIP) for signaling, and, more significantly, due to the lossy and capacity constrained wireless links. To address this challenge, we analyze the session setup delay end-to-end, by taking into account key system properties across all layers, ranging from radio links to IMS signaling architecture. We present a model for cross-layer performance analysis and simulation, which includes the statistical properties of the EV-DO (rev. A) wireless channel, and also takes into consideration the properties of transport protocols (TCP, UDP) and SIP signaling (message size and compression). By means of analysis and simulations, we study the setup delay performance of a generic, multi-operator IMS communication scenario between two mobile users. We describe how session setup delay can be estimated and reduced in realistic IMS settings and we propose architecture alternatives to the basic IMS scenario. The results derived from this study show that the proposed methods can incrementally lead to a lower setup delay and less sensitivity to the radio transmission quality and frame error rate compared to the base IMS scenario

Scheduling parallel loops, i.e., the way iterations are mapped on to different processors, plays a critical role in the efficient execution of programs, particularly of super-computing applications, on multiprocessor systems. In applications where the problem dimension (and hence execution time) is dependent on run-time data, loop iterations also tend to be of variable length - this variability affects both sequential and parallel loops and in particular nested loops and it is quite prevalent in sparse matrix solvers. In this paper, we propose a (execution) history-aware self-scheduling approach of irregular parallel loops on heterogeneous multiprocessor systems. First, the proposed method computes the chunk size, i.e., the amount of work allocated to a processor at each scheduling step, based on the variance in workload distribution across the iteration space. Second, it fine tunes the chunk size based on the execution history of the loop, wherein the workload of an iteration is determined at run-time based on the statistical deviation of workload estimates of previously executed iterations from their corresponding actual workloads. We evaluate our techniques using a set of kernels (extracted from industry-strength SPEC OMPM 2001 benchmark) with uneven workload distributions. The results show that our technique performs 5% -18% better than the existing schemes

Emergence of chip multiprocessors has created a need for exploitation of beyond DOALL-type thread-level parallelism (TLP). This calls for development of efficient thread synchronization techniques to exploit TLP in general parallel programs with dependences. For this, several thread synchronization techniques have been proposed in the past. However, these limit the exploitation of fine-grain TLP due to large run-time overhead. Furthermore, the existing approaches can potentially result in (i) deadlocks between the different threads and (ii) non-deterministic run-time execution behavior as these techniques are oblivious of the underlying memory model. In this paper, we propose lightweight lock-free thread synchronization methods to exploit TLP in general parallel programs with dependences. Each synchronization method intrinsically guarantees the following in a multithreaded program: (a) sequential consistency, (b) atomicity of writes to the shared synchronization construct and (c) absence of deadlocks. This reduces the programming effort considerably, thereby easing the development of software for multithreaded systems. For each method we formally prove that there cannot occur a deadlock between the different threads. This obviates the cumbersome and time-consuming process of detecting and eliminating deadlocks from the programmer. Experiments show that our synchronization methods incur a minimal overhead of 7.16% on an average. Further, we achieve performance speedups upto 3.39x on kernels extracted from the industry standard SPEC OMPM 2001 benchmarks, on a dedicated Intel® Xeon® 2.78 GHz 4-way multiprocessor.

Recent research in thread-level speculation (TLS) has proposed several mechanisms for optimistic execution of difficult-to-analyze serial codes in parallel. Though it has been shown that TLS helps to achieve higher levels of parallelism, evaluation of the unique performance potential of TLS, i.e., performance gain that be achieved only through speculation, has not received much attention. In this paper, we evaluate this aspect, by separating the speedup achievable via true TLP (thread-level parallelism) and TLS, for the SPEC CPU2000 benchmark. Further, we dissect the performance potential of each type of speculation --- control speculation, data dependence speculation and data value speculation. To the best of our knowledge, this is the first dissection study of its kind. Assuming an oracle TLS mechanism --- which corresponds to perfect speculation and zero threading overhead --- whereby the execution time of a candidate program region (for speculative execution) can be reduced to zero, our study shows that, at the loop-level, the upper bound on the arithmetic mean and geometric mean speedup achievable via TLS across SPEC CPU2000 is 39.16% (standard deviation = 31.23) and 18.18% respectively.

Parallel loops account for the greatest amount of parallelism in scientific and numerical codes. For example, most of the DO loops in SPEC CFP2000 and SPEC OMPM2001 are of DOALL type and account for a large percentage of the total execution time. One of the ways to exploit parallelism is to partition the iteration space of a DOALL loop amongst different processors in a parallel processor system. Naturally, a good partitioning is of key importance to achieve high performance and for efficient use of multiprocessor systems. Although a significant amount of work has been done in partitioning and scheduling of loops with both rectangular and non-rectangular iteration spaces, the problem of partitioning loops with conditionals has not been addressed so far to the best of our knowledge. In this paper, we present a mathematical model for partitioning parallel nested loops, both perfect and non-perfect, with conditionals, where the expressions in a conditional are affine functions of the outer loop indices. We present a loop transformation based on elimination of redundant constraints bounding the iteration space of a nested loop. The transformation plays a critical role during the (static) partitioning process as it helps to capture the "exact" lower and upper bounds (can be either a constant or symbolic) of the loop indices. We generate a canonical form of the loop nest using the transformation and employ the geometric approach we proposed earlier (in [1, 2]) for partitioning the iteration space along an axis corresponding to the outermost loop. For cases in which such a transformation does not exist, we propose a general approach for loop canonicalization. We present several examples from the literature and numerical packages to illustrate the effectiveness of our approach.

Efficient partitioning of parallel loops plays a critical role in high performance and efficient use of multiprocessor systems. Although a significant amount of work has been done in partitioning and scheduling of loops with rectangular iteration spaces, the problem of partitioning non-rectangular iteration spaces --- e.g., triangular, trapezoidal iteration spaces --- with variable densities has not been addressed so far to the best of our knowledge. In this paper, we present a mathematical model for partitioning N-dimensional non-rectangular iteration spaces with variable densities. We present a unimodular loop transformation and a geometric approach for partitioning an iteration space along an axis corresponding to the outermost loop across a given number of processors to achieve near-optimal performance, i.e., to achieve near-optimal load balance across different processors. We present a case study to illustrate the effectiveness of our approach.

Computational Network Federations (CNFs) enable an arbitrary set of heterogeneous hosts which are connected via any type of network to form dynamic virtual distributed systems that cooperate to execute an application, or serve as generalized application service platforms to end users. CNFs motivate a view of the Internet as a vast unified host: a repository of information, application services, and an omnipresent supercomputing resource regardless of the type of access device or access methodology. CNFs provide a powerful way of virtualizing generalized enterprise networks (or even the Internet), and an economic and resilient model for deploying enterprise applications, (such as CRM) and peer-2-peer services (e.g., chatrooms). This paper describes a middleware architecture that enables network-based computing, communications, and services through a unified, access, and platform-independent approach. CNFs borrow from the capabilities of grid computing and aim toward intelligent computational service networks that are ubiquitous, secure, and adaptive to user and access-method idiosyncrasies. CNFs encompass a set of abstractions and interfaces that provide: 1) a unified service-oriented view of the network to the user; 2) a homogeneous host abstraction to applications; and 3) a shared-memory abstraction to software developers. This paper outlines the architecture of CNFs and describes in more detail i-DVM, a distributed multithreaded meta-OS that forms the core of a CNF and implements the virtual machine abstraction and location transparency.

Much of the research in compiler design and optimization has traditionally focused on the effectiveness and efficiency of code optimization. However, the subject of efficiency of the entire compilation process itself (as opposed to the complexity of individual analysis or optimization algorithms) remains a highly complex and less investigated topic. In this paper we present a global approach to extensible and efficient compiler design, which aims at also improving the effectiveness and efficiency of analysis and optimization capabilities. Extensibility in complex compiler systems goes well beyond modularity of design and it needs to be considered from the early stages of the design, especially the design of the Intermediate Representation (IR). One of the primary barriers to compiler pass extensibility and modularity is interference between passes caused by transformations that invalidate existing analysis information. In this paper we also present a callback system which is provided to automatically track changes to the compiler's internal representation (IR) allowing full pass reordering and an easy-to-use interface for developing lazy update incremental analysis passes. We present a new algorithm for incremental interprocedural data flow analysis and demonstrate the benefits of our design framework and our prototype compiler system. It is shown that compilation time for multiple data flow analysis algorithms can be cut in half by incrementally updating data flow analysis. Our quantitative performance analysis is based on well-known benchmarks instead of random graphs like previous works. For smaller optimizations, order of magnitude improvements have been demonstrated. Our approach also simplifies design and implementation and hides many of the intricacies of a compiler's internal structures from the developer.

Abstract Distributed computing has become increasingly popular in the high‐performance community. Java's remote method invocation (RMI) provides a simple, yet powerful method for implementing parallel algorithms. The performance of RMI has been less than adequate, however, and object serialization is often identified as a major performance inhibitor. We believe that object serialization is best performed in the Java Virtual Machine (JVM), where information regarding object layout and hardware communication resources are readily available. We implement a subset of Java's object serialization protocol in native code, using the Java Native Interface (JNI) and JVM internals. Experiments show that our approach is up to eight times faster than Java's original object serialization protocol for array objects. Also, for linked data structures our approach obtains a moderate speedup and better scalability. Evaluation of our object serialization implementation in an RMI framework indicates that a higher throughput can be obtained. Parallel applications, written using RMI, obtain better speedups and scalability when this more efficient object serialization is used. Copyright © 2003 John Wiley & Sons, Ltd.

This paper presents scheduler extensions that enable better adaptation of parallel programs to the execution conditions of non-dedicated computational farms with limited memory resources. The purpose of the techniques is to prevent thrashing and co-schedule communicating threads, using two disjoint, yet cooperating extensions to the kernel scheduler. A thrashing prevention module enables memory-bound programs to adapt to memory shortage, via suspending their threads at selected points of execution. Thread suspension is used so that memory is not over-committed by parallel jobs—which are assumed to be running as guests on the nodes of the computational farm—at memory allocation points. In the event of thrashing, parallel jobs are the first to release memory and help local resident jobs make progress. Adaptation is implemented using a shared-memory interface in the /proc filesystem and upcalls from the kernel to the user space. On an orthogonal axis, co-scheduling is implemented in the kernel with a heuristic that boosts periodically the priority of communicating threads. Using experiments on a cluster of workstations, we show that when a guest parallel job competes with general-purpose interactive, I/O-intensive, or CPU and memory-intensive load on the nodes of the cluster, thrashing prevention reduces drastically the slowdown of the job at memory utilization levels of 20% or higher. The slowdown of parallel jobs is reduced by up to a factor of 7. Co-scheduling provides a limited performance improvement at memory utilization levels below 20%, but has no significant effect at higher memory utilization levels.

This paper presents scheduling techniques that enable the adaptation of parallel programs to clustered computational farms with limited memory capacity. The purpose of the techniques is to coschedule communicating processes and prevent paging, using two cooperating extensions to the kernel scheduler. A paging prevention module enables memory-bound programs to adapt to memory short-age, by suspending their threads at well-defined execution points. The associated operating system interface provides a generic mechanism that enables programs to adapt in different ways, including application-specific forms of adaptation. At the same time, a dynamic coscheduling heuristic implemented in the kernel scheduler increases periodically the priority of communicating processes so that parallel jobs are eased through communication points. We show that when a parallel job competes with randomized sequential load running in the nodes of the cluster, the combination of coscheduling and paging prevention reduces drastically the slowdown of the job at high levels of memory utilization. We also show that if memory resources are ample, coscheduling should take priority over paging prevention, whereas if memory resources are scarce, preventing paging should take priority over coscheduling.

This paper explores previously established and novel methods for scaling the performance of OpenMP on NUMA architectures. The spectrum of methods under investigation includes OS-level automatic page placement algorithms, dynamic page migrationd manual data distribution. The trade-off that these methods face lies between performance and programming effort. Automatic page placement algorithms are transparent to the programmer, but may compromise memory access locality. Dynamic page migration is also transparent, but requires careful engineering of online algorithms to be effective. Manual data distribution on the other requires substantial programming effort and architecture-specific extensions to OpenMP, but may localize memory accesses in a nearly optimal manner.

Recently popularized hardware multithreading (HMT) architectures, such as SMT, Multiscalar and Terra do not provide flexible and efficient methods of thread management and synchronization in hardware. The α-Coral architecture is a tool for investigation of a more dynamic approach to thread management. Unlike other architectures, there are no strict requirements on timing and size of threads, and no static partitioning of resources. α-Coral provides for simultaneous multiprogramming and multithreading environment, which is mostly managed in hardware. To other architectures, α-Coral adds on demand register allocation, fast variable size thread creation and destruction, as well as quick synchronization through a shared register file. While other architectures attempt to port existing compilers, the α-Coral architecture is supported by a custom compiler system. This system provides for a simple method of mapping hierarchical internal representation of the program to variable size threads.

We introduce nanoProtean, a new router operating system and execution environment that reduces system overhead, making it possible to process the packets produced by gigabit networks. The ovearhead decreases as the offered load per packet increases due to the following features in nanoProtean (i) a completely preemptable operating system, (ii) efficient management of the system's job queue, and (iii) system support for fine-grain sharing of processing time amongst packets. These features are a result of a novel integration of efficient thread scheduling for multiprocessors and interrupt handling. Experimental analysis used to test our systems scalability uses a technique to emulate processing requests generated in real-time at 802.3z (gigabit) line speeds and greater. Our results demonstrate 2 Gbps routing; with MAE-East tables on two processors, and system overheads decreasing from 3.6 /spl mu/s per packet to 1.64 /spl mu/s per packet on one processor. By reducing the system overhead, we also demonstrate that nanoProtean enables active networking in a router supporting gigabit connections.

The long foreseen goal of parallel programming models is to scale parallel code without significant programming effort. Irregular parallel applications are a particularly challenging application domain for parallel programming models, since they require domain specific data distribution and load balancing algorithms. From a performance perspective, shared-memory models still fall short of scaling as well as message-passing models in irregular applications, although they require less coding effort. We present a simple runtime methodology for scaling irregular applications parallelized with the standard OpenMP interface. We claim that our parallelization methodology requires the minimum amount of effort from the programmer and prove experimentally that it is able to scale two highly irregular codes as well as MPI, with an order of magnitude less programming effort. This is probably the first time such a result is obtained from OpenMP, more so, by keeping the OpenMP API intact.

This paper presents algorithms for improving the performance of parallel programs on multiprogrammed shared-memory NUMA multiprocessors, via the use of user-level dynamic page migration. The idea that drives the algorithms is that a page migration engine can perform accurate and timely page migrations in a multiprogrammed system if it can correlate page reference information with scheduling information obtained from the operating system. The necessary page migrations can be performed as a response to scheduling events that break the implicit association between threads and their memory affinity sets. We present two algorithms that use feedback from the kernel scheduler to aggressively migrate pages upon thread migrations. The first algorithm exploits the iterative nature of parallel programs, while the second targets generic codes without making assumptions on their structure. Performance evaluation on an SGI Origin2000 shows that our page migration algorithms provide substantial improvements in throughput of up to 264% compared to the native IRIX 6.5.5 page placement and migration schemes.

This paper presents user-level dynamic page migration, a runtime technique which transparently enables parallel pro-grams to tune their memory performance on distributed shared memory multiprocessors, with feedback obtained from dynamic monitoring of memory activity. Our technique exploits the iterative nature of parallel programs and information available to the program both at compile time and at runtime in order to improve the accuracy and the timeliness of page migrations, as well as amortize better the overhead, compared to page migration engines implemented in the operating system. We present an adaptive page migration algorithm based on a competitive and a predictive criterion. The competitive criterion is used to correct poor page placement decisions of the operating system, while the predictive criterion makes the algorithm respon-sive to scheduling events that necessitate immediate page migrations, such as preemptions and migrations of threads. We also present a new technique for preventing page ping-pong and a mechanism for monitoring the performance of page migration algorithms at runtime and tuning their sen-sitive parameters accordingly. Our experimental evidence on a SGI Origin2000 shows that unmodified OpenMP codes linked with our runtime system for dynamic page migration are effectively immune to the page placement strategy of the operating system and the associated problems with data locality. Furthermore, our runtime system achieves solid performance improvements compared to the IRIX 6.5.5 page migration engine, for single parallel OpenMP codes and multiprogrammed workloads.

This paper investigates the performance implications of data placement in OpenMP programs running on modern ccNUMA multiprocessors. Data locality and minimization of the rate of remote memory accesses are critical for sustaining high performance on these systems. We show that due to the low remote-to-local memory access latency ratio of state-of-the-art ccNUMA architectures, reasonably balanced page placement schemes, such as round-robin or random distribution of pages incur modest performance losses. We also show that performance leaks stemming from suboptimal page placement schemes can be remedied with a smart user-level page migration engine. The main body of the paper describes how the OpenMP runtime environment can use page migration for implementing implicit data distribution and redistribution schemes without programmer intervention. Our experimental results support the effectiveness of these mechanisms and provide a proof of concept that there is no need to introduce data distribution directives in OpenMP and warrant the portability of the programming model.

The memory hierarchy of high-performance and embedded processors has been shown to be one of the major energy consumers. For example, the Level-1 (L1) instruction cache (I-Cache) of the StrongARM processor accounts for 27% of the power dissipation of the whole chip, whereas the instruction fetch unit (IFU) and the I-Cache of Intel's Pentium Pro processor are the single most important power consuming modules with 14% of the total power dissipation [2]. Extrapolating current trends, this portion is likely to increase in the near future, since the devices devoted to the caches occupy an increasingly larger percentage of the total area of the chip. In this paper, we propose a technique that uses an additional mini cache, the LO-Cache, located between the I-Cache and the CPU core. This mechanism can provide the instruction stream to the data path and, when managed properly, it can effectively eliminate the need for high utilization of the more expensive I-Cache. We propose, implement, and evaluate five techniques for dynamic analysis of the program instruction access behavior, which is then used to proactively guide the access of the LO-Cache. The basic idea is that only the most frequently executed portions of the code should be stored in the LO-Cache since this is where the program spends most of its time. We present experimental results to evaluate the effectiveness of our scheme in terms of performance and energy dissipation for a series of SPEC95 benchmarks. We also discuss the performance and energy tradeoffs that are involved in these dynamic schemes. Results for these benchmarks indicate that more than 60% of the dissipated energy in the I-Cache subsystem can be saved.

In this paper, we focus on low-power design techniques for high-performance processors at the architectural and compiler levels. We focus mainly on developing methods for reducing the energy dissipated in the on-chip caches. Energy dissipated in caches represents a substantial portion in the energy budget of today's processors. Extrapolating current trends, this portion is likely to increase in the near future, since the devices devoted to the caches occupy an increasingly larger percentage of the total area of the chip. We propose a method that uses an additional minicache located between the I-Cache and the central processing unit (CPU) core and buffers instructions that are nested within loops and are continuously otherwise fetched from the I-Cache. This mechanism is combined with code modifications, through the compiler, that greatly simplify the required hardware, eliminate unnecessary instruction fetching, and consequently reduce signal switching activity and the dissipated energy. We show that the additional cache, dubbed L-Cache, is much smaller and simpler than the I-Cache when the compiler assumes the role of allocating instructions to it. Through simulation, we show that for the SPECfp95 benchmarks, the I-Cache remains disabled most of the time, and the "cheaper" extra cache is used instead. We also propose different techniques that are better adapted to nonnumeric nonloop-intensive code.

Energy dissipated in on-chip caches represents a substantial portion in the energy budget of today's processors. Extrapolating current trends, this portion is likely to increase in the near future, since the devices devoted to the caches occupy an increasingly larger percentage of the total area of the chip. We extend the work proposed by J. Kin et al. (1997), in which an extra, small cache (called filter cache) is inserted between the CPU data path and the L1 cache and serves to filter most of the references initiated from the CPU. In our scheme, the compiler is used to generate code that exploits the new memory hierarchy and reduces the possibility of a miss in the extra cache. Experimental results across a wide range of SPEC95 benchmarks show that this cache, which we call L-Cache, has a small performance overhead with respect to the scheme without any extra caches, and provides substantial energy savings. The L-Cache is placed between the CPU and the I-Cache. The D-Cache subsystem is not modified. Since the L-Cache is much smaller, and thus, has a smaller access time than the I-Cache, this scheme can also be used for performance improvements provided that the hit rate in the L-Cache is very high. In our experimental results, we show that the L-Cache does indeed improve performance in some cases.

Article Using dynamic cache management techniques to reduce energy in a high-performance processor Share on Authors: Nikolaos Bellas Department of Electrical & Computer Engineering and the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 1308 West Main Street, Urbana, IL Department of Electrical & Computer Engineering and the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 1308 West Main Street, Urbana, ILView Profile , Ibrahim Hajj Department of Electrical & Computer Engineering and the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 1308 West Main Street, Urbana, IL Department of Electrical & Computer Engineering and the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 1308 West Main Street, Urbana, ILView Profile , Constantine Polychronopoulos Department of Electrical & Computer Engineering and the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 1308 West Main Street, Urbana, IL Department of Electrical & Computer Engineering and the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 1308 West Main Street, Urbana, ILView Profile Authors Info & Claims ISLPED '99: Proceedings of the 1999 international symposium on Low power electronics and designAugust 1999 Pages 64–69https://doi.org/10.1145/313817.313856Online:17 August 1999Publication History 59citation448DownloadsMetricsTotal Citations59Total Downloads448Last 12 Months6Last 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

In this paper we propose a technique that uses an additional mini cache located between the I-Cache and the CPU core, and buffers instructions that are nested within loops and are continuously otherwise fetched from the I-Cache. This mechanism is combined with code modifications, through the compiler, that greatly simplify the required hardware, eliminate unnecessary instruction fetching, and consequently reduce signal switching activity and the dissipated energy.

The notion of dependence captures that most important properties of a program for efficient execution on parallel computers. The dependence structure of a program defines that necessary constraints of the order of execution of the program components and provides sufficient information for the exploitation of the available parallelism. Static discovery and management of the dependence structure of programs save a tremendous amount of execution time, and dynamic utilization of dependence information results in a significant performance gain on parallel computers. However, experiments with parallel computers indicate that existing multiprocessing environments are unable to deliver the desired performance over a wide range of real applications, mainly due to lack of precision of their dependence information. This calls for an effective compilation scheme capable of understanding the dependence structure of complicated application programs. This article describes a methodology for capturing analyzing program properties that are essential in the effective detection and efficient exploitation of parallelism on parallel computers. Based on this methodology, a symbolic analysis framework is developed for the Parafrase-2 parallelizing compiler. This framework extends the scope of a variety of important program analysis problems and solves them in a unified way. The attained solution space of these problems is much larger than that handled by existing compiler technology. Such a powerful approach is required for the effective compilation of a large class of application programs.

This paper discusses the comprehensive performance profiling, improvement and benchmarking of a Computational Fluid Dynamics code, one of the Grand Challenge applications, on three popular multiprocessors. In the process of analyzing performance we considered language, compiler, architecture, and algorithmic changes and quantified each of them and their incremental contribution to bottom-line performance. We demonstrate that parallelization alone cannot result in significant gains if the granularity of parallel threads and the effect of parallelization on data locality are not taken into account. Unlike benchmarking studies that often focus on the performance or effectiveness of parallelizing compilers on specific loop kernels, we used the entire CFD code to measure the global effectiveness of compilers and parallel architectures. We probed the performance bottlenecks in each case and derived solutions which eliminate or neutralize the performance inhibiting factors. The major conclusion of our work is that overall performance is extremely sensitive to the synergetic effects of compiler optimizations, algorithmic and code tuning, and architectural idiosyncrasies.

Automatic detection of task-level parallelism (also referred to as functional, DAG, unstructured, or thread parallelism) at various levels of program granularity is becoming increasingly important for parallelizing and back-end compilers. Parallelizing compilers detect iteration-level or coarser granularity parallelism which is suitable for parallel computers; detection of parallelism at the statement-or operation-level is essential for most modern microprocessors, including superscalar and VLIW architectures. In this article we study the problem of detecting, expressing, and optimizing task-level parallelism, where “task” refers to a program statement of arbitrary granularity. Optimizing the amount of functional parallelism (by allowing synchronization between arbitrary nodes) in sequential programs requires the notion of precedence in terms of paths in graphs which incorporate control and data dependences. Precedences have been defined before in a different context; however, the definition was dependent on the ideas of parallel execution and time. We show that the problem of determining precedences statically is NP-complete. Determining precedence relationships is useful in finding the essential data dependences. We show that there exists a unique minimum set of essential data dependences; finding this minimum set is NP-hard and NP-easy. We also propose a heuristic algorithm for finding the set of essential data dependences. Static analysis of a program in the Perfect Benchmarks was done, and we present some experimental results.

No abstract available.

Presents the hierarchical task graph (HTG) as an intermediate parallel program representation which encapsulates minimal data and control dependences, and which can be used for the extraction and exploitation of functional, or task-level parallelism. The hierarchical nature of the HTG facilitates efficient task-granularity control during code generation, and thus applicability to a variety of parallel architectures. The construction of the HTG at a given hierarchy level, the derivation of the execution conditions of tasks which maximizes task-level parallelism, and the optimization of these conditions which results in reducing synchronization overhead imposed by data and control dependences are emphasized. Algorithms for the formation of tasks and their execution conditions based on data and control dependence constraints are presented. The issue of optimization of such conditions is discussed, and optimization algorithms are proposed. The HTG is used as the intermediate representation of parallel Fortran and C programs for generating parallel source as well as parallel machine code.>

Article The hierarchical task graph and its use in auto-scheduling Share on Author: Constantine D. Polychronopoulos Center for Supercomputing Research and Development, Dept. of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, Illinois Center for Supercomputing Research and Development, Dept. of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IllinoisView Profile Authors Info & Claims ICS '91: Proceedings of the 5th international conference on SupercomputingJune 1991 Pages 252–263https://doi.org/10.1145/109025.109089Online:01 June 1991Publication History 16citation685DownloadsMetricsTotal Citations16Total Downloads685Last 12 Months14Last 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

A special-purpose hardware scheme uniquely tailored to barrier synchronization is presented. It allows barrier synchronization to be performed within a single instruction cycle for moderately sized systems, and is scalable with logarithmic increase in synchronization time. It supports a large number of concurrent barriers, and can also be used to support a number of different barrier synchronization schemes. The hardware is relatively simple and inexpensive. Simulation results have shown that, under reasonable assumptions, it can decrease typical parallel-loop execution time significantly, especially for fine-grained and statically scheduled loops.>

While much work has been done to date on the study of task-scheduling schemes for shared memory machines, little of the knowledge gained has been transferred to distributed memory systems. In this paper we discuss the implementation and performance evaluation of various scheduling schemes (which have been widely used on shared memory systems) on the Intel iPSC/2 hypercube. Two benchmarks representing the two ends of the spectrum with respect to task sizes were used to carry out the experiments. The primary goal of this work was to test the performance of guided self-scheduling (GSS) [PoKu87] against other commonly used schemes, and implement an efficient dynamic loop scheduling mechanism on a hypercube. The results suggest that GSS would be a far more efficient and consistent scheduling mechanism for hypercube architectures, and across the range of applications.

General purpose parallel processing machines are increasingly being used to speed up a variety of VLSI CAD applications. This paper addresses logic simulation on parallel machines by exploiting the concurrency in the circuit being simulated (called data parallelism) as opposed to exploiting parallelism inherent in the simulation algorithm itself (called functional parallelism). The most crucial step in obtaining the maximum parallelism using data parallelism is the partitioning of circuit elements. We introduce a cost function which tries to model the simulation of a logic circuit in a parallel environment. The cost function tries to estimate the parallel run time for logic simulation given the processor assignment and the underlying multiprocessor architecture. We then present different heuristic algorithms to partition the circuit and evaluate the efficiency of these algorithms using the proposed cost function. Partitioning algorithms for both event-driven and compiled code simulation are given.

Program parallelism and processor allocation issues for parallel processor systems are discussed. Optimal processor assignment algorithms are presented for simple and complex nested parallel loops. These processor assignment schemes can be used by the compiler to perform static processor allocation to multiply nested parallel loops. Speedup measurements for EISPACK and IEEE DSP subroutines that result from the optimal assignment of processors to parallel loops are also presented. These measurements indicate that optimal processor assignments result in almost linear speedups on parallel processor machines with a few tens of processes and significantly high speedups for machines with hundreds or thousands of processors.>

The ability of parallel computers to execute multiple instruction streams (tasks) simultaneously gives rise to the problem of partitioning a program into a set of tasks that can be assigned to different processors. The degree to which parallelism can be exploited, the amount of overhead involved during parallel execution of a program and a number of other factors depend directly on partitioning. A good partitioning scheme must take into account all these factors. In this paper we present algorithms to compute optimal partitions in diverse models of the problem. Both directed and undirected graph representations of a parallel program are considered. For some instances of the problem where practical optimal schemes are not possible we suggest simple and efficient heuristics. Finally, a polynomial time algorithm to compute optimal partitions for chains is given.

Two issues for supercomputer compilers are considered. Exact and inexact tests for computing data dependences and focus on the linearization scheme are first discussed. A program transformation call loop spreading is then presented that can be used to execute in parallel adjacent loops with interloop dependences.>

By examining the structure and characteristics of parallel programs the author isolates potential overhead sources. The first compiler optimization considered is cycle shrinking which can be used to parallelize certain types of serial loops. A run-time dependence analysis is then considered along with how it can be performed through compiler-inserted bookkeeping and control statements. Loops with unstructured parallelism, that cannot benefit from existing optimizations, can be parallelized through run-time dependence checking. Finally, barrier synchronization is discussed as one of the most serious sources of run-time overhead in parallel programs. To reduce the impact of barriers, the author briefly discusses the implementation of distributed barriers through the use of a set of shared registers.>

The main aim of the paper is to study allocation of processors to, parallel programs executing on a multiprocessor system, and the resulting speedups. First, we consider a parallel program as a sequence of steps where each step consists of a set of parallel operations. General bounds on the speedup on a p- processor system are derived based on this model. Measurements of code parallelism for the, LINPACK numerical package are presented to support the belief that typical numerical programs contain much potential parallelism that can be discovered by a good restructuring compiler. Next, a parallel program is represented as a task graph whose nodes are do across loops (i.e., loops whose iterations can be partially, overlapped). It is shown how processors can be allocated to exploit horizontal and vertical parallelism in such graphs. Two processor allocation heuristic algorithms (WP and PA) are presented. PA is the heart of the WP and is used to obtain efficient processor allocations for a set of independent parallel tasks. WP allocates processors to general task graphs. Finally, a general formula for the speedup of a DO across loop is given that is more accurate than the known formula.

This paper proposes guided self-scheduling, a new approach for scheduling arbitrarily nested parallel program loops on shared memory multiprocessor systems. Utilizing loop parallelism is clearly most crucial in achieving high system and program performance. Because of its simplicity, guided self-scheduling is particularly suited for implementation on real parallel machines. This method achieves simultaneously the two most important objectives: load balancing and very low synchronization overhead. For certain types of loops we show analytically that guided self-scheduling uses minimal overhead and achieves optimal schedules. Two other interesting properties of this method are its insensitivity to the initial processor configuration (in time) and its parameterized nature which allows us to tune it for different systems. Finally we discuss experimental results that clearly show the advantage of guided self-scheduling over the most widely known dynamic methods.