A new package-level interconnect is described that adapts carbon nanoemissive display technology to create an inexpensive package-level freespace crossbar with single-cycle source-to-target latency. Interconnections are made using filamentary electron beams as the data transmission medium. The beams are electrostatically steered, enabling very large, low latency inter-chip crossbar networks. The crossbar and associated package are built entirely from existing technology. This paper describes the operation of the crossbar and presents a conceptual design for a processor that uses the crossbar.

Predicated execution enables the removal of branches by converting segments of branching code into sequences of conditional operations. An important side effect of this transformation is that the compiler must unconditionally assign resources to predicated operations. However, a resource is only put to productive use when the predicate associated with an operation evaluates to True. To reduce this superfluous commitment of resources, we propose probabilistic predicate-aware scheduling to assign multiple operations to the same resource at the same time, thereby over-subscribing its use. Assignment is performed in a probabilistic manner using a combination of predicate profile information and predicate analysis aimed at maximizing the benefits of over-subscription in view of the expected degree of conflict. Conflicts occur when two or more operations assigned to the same resource have their predicates evaluate to True. A predicate-aware VLIW processor pipeline detects such conflicts, recovers, and correctly executes the conflicting operations. By increasing the effective throughput of a fixed set of resources, probabilistic predicate-aware scheduling provided an average of 20% performance gain in our evaluations on a 4-issue processor, and 8% gain on a 6-issue processor.

The growing difference between processor and main memory cycle time demands the use of aggressive prefetch algorithms to reduce the effective memory access latency. However, prefetching can significantly increase memory traffic and unsuccessful prefetches may pollute the cache. Metrics such as coverage and accuracy result from a simplistic classification of individual prefetches as "good" or "bad." They do not capture the full effect of each prefetch and, hence, do not accurately reflect the quality of the prefetch algorithm. Gross statistics such as changes in the number of misses, total traffic, and IPC are not attributable to individual prefetches. Such gross metrics are therefore useful only for ranking existing prefetch algorithms; they do not evaluate the effect of individual prefetches so that an algorithm might be tuned. We introduce a new, accurate, and complete taxonomy, called the Prefetch Traffic and Miss Taxonomy (PTMT), for classifying each prefetch by precisely accounting for the difference in traffic and misses it generates, either directly or indirectly. We illustrate the use of PTMT by evaluating two data prefetch algorithms.

Predicated execution enables the removal of branches wherein segments of branching code are converted into straight-line segments of conditional operations. An important, but generally ignored side effect of this transformation is that the compiler must assign distinct resources to all the predicated operations at a given time to ensure that those resources are available at run-time. However, a resource is only put to productive use when the predicates associated with its operations evaluate to True. We propose predicate-aware scheduling to reduce the superfluous commitment of resources to operations whose predicates evaluate to False at run-time. The central idea is to assign multiple operations to the same resource at the same time, thereby oversubscribing its use. This assignment is intelligently performed to ensure that no two operations simultaneously assigned to the same resource will have both of their predicates evaluate to True. Thus, no resource is dynamically oversubscribed. The overall effect of predicate aware scheduling is to use resources more efficiently, thereby increasing performance when resource constraints are a bottleneck.

With the continuing technological trend of ever cheaper and larger memory, most data sets in database servers will soon be able to reside in main memory. In this configuration, the performance bottleneck is likely to be the gap between the processing speed of the CPU and the memory access latency. Previous work has shown that database applications have large instruction and data footprints and hence do not use processor caches effectively. In this paper, we propose Call Graph Prefetching (CGP), an N instruction prefetching technique that analyzes the call graph of a database system and prefetches instructions from the function that is deemed likely to be called next. CGP capitalizes on the highly predictable function call sequences that are typical of database systems. CGP can be implemented either in software or in hardware. The software-based CGP ( CGP_S ) uses profile information to build a call graph, and uses the predictable call sequences in the call graph to determine which function to prefetch next. The hardware-based CGP( CGP_H ) uses a hardware table, called the Call Graph History Cache (CGHC), to dynamically store sequences of functions invoked during program execution, and uses that stored history when choosing which functions to prefetch.We evaluate the performance of CGP on sets of Wisconsin and TPC-H queries, as well as on CPU-2000 benchmarks. For most CPU-2000 applications the number of instruction cache (I-cache) misses were very few even without any prefetching, obviating the need for CGP. On the other hand, the database workloads do suffer a significant number of I-cache misses; CGP_S improves their performance by 23% and CGP_H by 26% over a baseline system that has already been highly tuned for efficient I-cache usage by using the OM tool. CGP, with or without OM, reduces the I-cache miss stall time by about 50% relative to O5+OM, taking us about half way from an already highly tuned baseline system toward perfect I-cache performance.

Although x86 processors have been around for a long time and are the most ubiquitous processors in the world, the amount of academic research regarding details of their performance has been minimal. We introduce an x86 simulation environment, called TAXI (Trace Analysis for X86 Interpretation), and use it to present results for eight Win32 applications. In this paper, we explain the design and implementation of TAXI.

Trace caches are used to help dynamic branch prediction make multiple predictions in a cycle by embedding some of the predictions in the trace. In this work, we evaluate a trace cache that is capable of delivering a trace consisting of a variable number of instructions via a linked list mechanism. We evaluate several schemes in the context of an x86 processor model that stores decoded instructions. By developing a new classification for trace cache accesses, we are able to target those misses that cause the largest performance loss. We have proposed a hardware speculation technique, called NonHead Miss Speculation, which removes much of the penalty associated with nonhead misses in the eight applications we studied. Performance improvements ranged from 2% to 20%, with an average speedup of around 10% across our application suite.

With the continuing technological trend of ever cheaper and larger memory, most data sets in database servers will soon be able to reside in main memory. In this configuration, the performance bottleneck is likely to be the gap between the processing speed of the CPU and the memory access latency. Previous work has shown that database applications have large instruction and data footprints and hence do not use processor caches effectively. In this paper we propose Call Graph Prefetching (CGP), a hardware technique that analyzes the call graph of a database system and prefetches instructions from the function that is deemed likely to be called next. CGP capitalizes on the highly predictable function call sequences that are typical of database systems. We evaluate the performance of CGP on sets of Wisconsin and TPC-H queries, as well as on CPU-2000 benchmarks. For most CPU-2000 applications the number of l-cache misses were very few even without any prefetching, obviating the need for CGP. Our database experiments show that CGP reduces the I-cache misses by 83% and can improve the performance of a database system by 30% over a baseline system that uses the OM tool to layout the code so as to improve I-cache performance. CGP also achieved 7% higher performance than OM with next-N-line prefetching on database applications.

Instruction cache misses stall the fetch stage of the processor pipeline and hence affect instruction supply to the processor. Instruction prefetching has been proposed as a mechanism to reduce instruction cache (I-cache) misses. However, a prefetch is effective only if accurate and initiated sufficiently early to cover the miss penalty. This paper presents a new hardware-based instruction prefetching mechanism, Branch History Guided Prefetching (BHGP), to improve the timeliness of instruction prefetches. BHGP correlates the execution of a branch instruction with I-cache misses and uses branch instructions to trigger prefetches of instructions that occur (N-1) branches later in the program execution, for a given N>1. Evaluations on commercial applications, windows-NT applications, and some CPU2000 applications show an average reduction of 66% in miss rate over all applications. BHGP improved the IPC bp 12 to 14% for the CPU2000 applications studied; on average 80% of the BHGP prefetches arrived in cache before their next use, even on a 4-wide issue machine with a 15 cycle L2 access penalty.

Several schemes have been proposed that incorporate an auxiliary buffer to improve the performance of a given size cache. Victim caching, aims to reduce the impact of conflict misses in direct-mapped caches. Victim offers competitive performance benefits, but requires a costly data path for swaps and saves between the main cache and the added buffer. Several multilateral schemes (e.g. NTS, PCS) offer competitive performance with Victim across a wide range of associativities, but require no swap/save data path. While these schemes perform well overall, their overall performance lags that of Victim when the main cache is direct-mapped. Furthermore, they also require costly hardware support, but in the form of history tables for maintaining allocation decision information. The paper introduces a multilateral cache management scheme, allocation by conflict (ABC), which generally outperforms Victim, NTS, and PCS. Furthermore, ABC has the lowest hardware requirements of any multilateral scheme-only a single additional bit per block in the main cache is required to maintain usage information for the allocation decision process, and no swap/save data path is needed.

Data cache misses reduce the performance of wide-issue processors by stalling the data supply to the processor. Prefetching data by predicting the miss address is one way to tolerate the cache miss latencies. But current applications with irregular access patterns make it difficult to accurately predict the address sufficiently early to mask large cache miss latencies. This paper explores an alternative to predicting prefetch addresses, namely precomputing them. The Dependence Graph Precomputation scheme (DGP) introduced in this paper is a novel approach for dynamically identifying and precomputing the instructions that determine the addresses accessed by those load/store instructions marked as being responsible for most data cache misses. DGP's dependence graph generator efficiently generates the required dependence graphs at run time. A separate precomputation engine executes these graphs to generate the data addresses of the marked load/store instructions early enough for accurate prefetching. Our results show that 94% of the prefetches issued by DGP are useful, reducing the D-cache miss stall time by 47%. Thus DGP takes us about half way from an already highly tuned baseline system toward perfect D-cache performance. DGP improves the overall performance of a wide range of applications by 7% over tagged next line prefetching, by 13% over a baseline processor with no prefetching, and is within 15% of the perfect D-cache performance.

In this paper, we examine the effectiveness of a new hardware mechanism, called register queues (RQs), which effectively decouples the architected register space from the physical registers. Using RQs, the compiler can allocate physical registers to store live values in the software pipelined loop while minimizing the pressure placed on architected registers. We show that decoupling the architected register space from the physical register space can greatly increase the applicability of software pipelining, even as memory latencies increase. RQs combine the major aspects of existing rotating register file and register connection techniques to generate efficient software pipeline schedules. Through the use of RQs, we can minimize the register pressure and code expansion caused by software pipelining. We demonstrate the effect of incorporating register queues and software pipelining with 983 loops taken from the Perfect Club, the SPEC suites, and the Livermore Kernels.

To reduce software development and maintenance costs, programmers are increasingly using object oriented programming languages, such as C++, and relying on highly flexible data structures, such as linked lists. Object oriented programming languages provide features that help manage complex software systems, but object oriented programs tend to suffer increased instruction counts, e.g. due to generalized class implementations and many more calls to small functions. Using linked data structures increases programming flexibility by allowing easy addition and deletion of nodes, and by dynamically allocating memory to satisfy applications that use large memory space. However, successive elements in linked data structures may be allocated noncontinuously in memory, leading to poor spatial locality for list traversals which in turn increases cache misses and reduces performance. This paper evaluates the impact of both the increased instruction overhead and poor spatial locality on superscalar processor performance as issue width increases. We show that underutilized resources of wide-issue processors can partially alleviate the impact of the instruction overhead. However, poor locality tends to cause more performance degradation as the processor issue width increases. Finally we show that the spatial locality of some programs can be improved by using a vector representation to replace linked list structures. Vectors exhibit better spatial locality during list traversals, but suffer from instruction overhead and memory copy overhead when nodes are added to and deleted from the structure.

Dynamically Linked Libraries (DLLs) promote software modularity, portability, and flexibility and their use has become widespread. The authors characterize the behavior of five applications that make heavy use of DLLs, with a particular focus on the effects of DLLs on Branch Target Buffer (BTB) performance. DLLs aggravate hot set contention in the BTB. Standard software remedies are ineffective because the DLLs are shared, compiled separately, and dynamically linked to applications. We propose a hardware technique, the DLL BTB, that adds a small second buffer to the BTB and dedicates it to storing DLL target addresses. We show that the DLL BTB performance is similar to a BTB with a victim buffer, but the DLL BTB requires no parallel lookups or datapaths between the original BTB and the added buffer.

University of Michigan

As microprocessor speeds continue to outpace memory subsystems in speed, minimizing average data access time grows in importance. Multilateral caches afford an opportunity to reduce the average data access time by active management of block allocation and replacement decisions. We evaluate and compare the performance of traditional caches and multilateral caches with three active block allocation schemes: MAT, NTS, and PCS. We also compare the performance of NTS and PCS to multilateral caches with a near-optimal, but nonimplementable policy, pseudo-opt, that employs future knowledge to achieve both active allocation and active replacement. NTS and PGS are evaluated relative to pseudo-opt with respect to miss ratio, accuracy of predicting reference locality, actual usage accuracy, and tour lengths of blocks in the cache. Results show that the multilateral schemes do outperform traditional cache management schemes, but fall short of pseudo-opt; increasing their prediction accuracy and incorporating active replacement decisions would allow them to more closely approach pseudo-opt performance.

In this paper we examine the performance of two multi-lateral cache schemes; one makes block allocation decisions correlated to the reference behavior of regions of memory (NTS), the other correlated to the reference behavior of memory accessing instructions (PCS). To determine the efficacy of exploiting these reference correlation schemes to improve cache management, we compare the performance of these multi-lateral schemes to a multi-lateral configuration that uses a near-optimal (but non-implementable) replacement policy, pseudo-opt. In addition to miss ratio, three metrics are used to evaluate the performance of these schemes, relative to pseudo-opt: 1) prediction accuracy in determining reference locality, 2) actual usage accuracy, i.e. how likely a block in an implementable scheme and the near-optimal scheme exhibit the same reuse characteristic, and 3) tour length of a line in the cache. Results show that while the NTS and PCS schemes outperform traditional cache management schemes, they fall short of the pseudo-opt performance; this is due to their simple prediction strategies and because their active management addresses only block allocation and not replacement.

As microprocessor speeds continue to outgrow memory subsystem speeds, minimizing the average data access time grows in importance. As current data caches are often poorly and inefficiently managed, a good management technique can improve the average data access time. This paper presents a comparative evaluation of two approaches that utilize reuse information for more efficiently managing the firstlevel cache. While one approach is based on the effective address of the data being referenced, the other uses the program counter of the memory instruction generating the reference. Our evaluations show that using effective address reuse information performs better than using program counter reuse information. In addition, we show that the Victim cache performs best for multi-lateral caches with a direct-mapped main cache and high L2 cache latency, while the NTS (effective-addressbased) approach performs better as the L2 latency decreases or the associativity of the main cache increases.

Advances in microarchitecture, packaging, and manufacturing processes enable designers to build new systems with higher performance and scalability. Using microbenchmark techniques, we contrast the memory and communication performance of two generations of the HP/Convex Exemplar scalable parallel processing system. The SPP1000 and SPP2000 have significant architectural and implementation differences, but maintain upward binary compatibility. The SPP2000 employs manufacturing and packaging advances to obtain shorter system interconnects with wider data paths and improved functionality thereby reducing the latency and increasing the bandwidth of remote communication. Although the memory latency is not significantly improved, newer out-of-order execution processors coupled with nonblocking caches achieve much higher memory bandwidth. The SPP2000 has a richer system interconnect topology that allows scalability to a larger number of processors. The SPP2000 also employs innovations in its coherence protocols to improve synchronization and communication performance. This paper characterizes the performance effects of these changes, and identifies some remaining inefficiencies, in the cache coherence protocol and the node configuration, that future systems should address.

As the gap between processor and memory speeds increases, cache performance becomes more critical to overall system performance. Multi-lateral cache designs such as the Assist, Victim, and NTS cache have been shown to perform as well as or better than larger, single structure caches. Unlike current cache simulators, mlcache (an event-driven, timing-sensitive simulator based on the Latency Effects cache timing model) can evaluate a variety of multilateral cache configurations. It was developed to help designers in the middle of the design cycle decide which cache configuration would best meet the performance needs of the target processor. It can easily model various cache configurations by using its library of cache state and data movement routines. We use the SPEC95 benchmarks to illustrate how mlcache can be used to compare the performance of several different data cache configurations.

In a distributed shared memory (DSM) multiprocessor, the processors cooperate in solving a parallel application by accessing the shared memory. The latency of a memory access depends on several factors, including the distance to the nearest valid data copy, data sharing conditions, and traffic of other processors. To provide a better understanding of DSM performance and to support application tuning and compiler development for DSM systems, this paper extends microbenchmarking techniques to characterize the important aspects of a DSM system. We present an experiment-based methodology for characterizing the memory, communication, scheduling, and synchronization performance, and apply it to the Convex SPP1000. We present carefully designed microbenchmarks to characterize the performance of the local and remote memory, producer-consumer communication involving two or more processors, and the effects on performance when multiple processors contend for utilization of the distributed memory and the interconnection network.

Emerging multi-issue microprocessors require effective data supply to sustain multiple instruction processing. The data cache structure, the backbone of data supply, has been organized and managed as one large homogenous resource, offering little flexibility for selective caching. While memory latency hiding techniques and multi-ported caches are critical to effective data supply, we show in this paper that even ideal non-blocking multi-ported caches fail to be sufficient in and of themselves in supplying data. We evaluate an approach in which the first level (L1) data cache is partitioned into multiple (multi-lateral) subcaches. The data reference stream of a running program is subdivided into two classes, and each class is mapped to a specific subcache whose management policy is more suitable for the access pattern of its class. This sort of selective organization and caching retains more useful data in the L1 Cache, which translates to more cache hits, less cache-memory bus contention and overall improvement in execution time. Our simulations show that a multi-lateral L1 cache of (8+1)KB total size generally performs as well as, and in some cases better than, an ideal multiported 16 KB cache structure in supplying data.

Highly aggressive multi-issue processor designs of the past few years and projections for the next decade require that we redesign the operation of the cache memory system. The number of instructions that must be processed (including correctly predicted ones) will approach 16 or more per cycle. Since memory operations account for about a third of all instructions executed these systems will have to support multiple data references per cycle. We explore reference stream characteristics to determine how best to meet the need for ever increasing access rates. We identify limitations of existing multi-ported cache designs and propose a new structure, the locality-based interleaved cache (LBIC), to exploit the characteristics of the data reference stream while approaching the economy of traditional multi-bank cache design. Experimental results show that the LBIC structure is capable of outperforming current multi-ported approaches.

Modulo scheduling algorithms based on optimal solvers have been proposed to investigate and tune the performance of modulo scheduling heuristics. While recent advances have broadened the scope for which the optimal approach is applicable, this approach increasingly suffers from large execution times. In this paper, we propose a more efficient formulation of the modulo scheduling space that significantly decreases the execution time of solvers based on integer linear programs. For example, the total execution time is reduced by a factor of 8.6 when 782 loops from the Perfect Club, SPEC, and Livermore Fortran Kernels are scheduled for minimum register requirements using the more efficient formulation instead of the traditional formulation. Experimental evidence further indicates that significantly larger loops can be scheduled under realistic machine constraints.

Article Free Access Share on Profile driven weighted decomposition Authors: Karen A. Tomko Department of Computer Science and Engineering, Wright State University, Dayton, OH Department of Computer Science and Engineering, Wright State University, Dayton, OHView Profile , Edward S. Davidson Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MIView Profile Authors Info & Claims ICS '96: Proceedings of the 10th international conference on SupercomputingJanuary 1996Pages 165–172https://doi.org/10.1145/237578.237600Published:01 January 1996Publication History 1citation202DownloadsMetricsTotal Citations1Total Downloads202Last 12 Months11Last 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 Publisher SiteeReaderPDF

High performance compilers increasingly rely on accurate modeling of the machine resources to efficiently exploit the instruction level parallelism of an application. In this paper, we propose a reduced machine description that results in faster detection of resource contentions while preserving the scheduling constraints present in the original machine description. The proposed approach reduces a machine description in an automated, error-free, and efficient fashion, Moreover, it fully supports schedulers that backtrack and process operations in arbitrary order. Reduced descriptions for the DEC Alpha 21064, MIPS R3000/R3010, and Cydra 5 result in 4 to 7 times faster detection of resource contentions and require 22 to 90% of the memory storage used by the original machine descriptions. Precise measurement for the Cydra 5 indicates that reducing the machine description results in a 2.9 times faster contention query module.

In this paper we propose a new execution trace driven simulation technique, called the Resource Conflict Methodology (RCM) for modeling and simulating computer systems early in the design cycle. By using a simplified hardware element model which allows the user to easily add or delete hardware elements in the model, RCM allows the user to readily change the machine design being investigated and to evaluate the resulting machine on a given workload. We describe the RCM model with reference to a family of superscalar processors and develop an RCM-based analysis program (called REAP) for this family of processors. Using REAP, we demonstrate the validity of our method by comparing its RCM performance estimates to those of a traditional early design stage timer model.

Modtdo schedulwsg is an eficient tech nzque for exploiting instruction level parallelism in a uaraety of ioopsl resulting in high performance code but increased register requirements.We present a combined approach that schedules the loop operations for the highest steady state throughput and minimum register requirements.Our method determines optimal register requirements for machines with jinite resources and for general dependence graphs.We compare the performance of this and other modulo schedulers for a benchmark of 6.29 loops from the Perfect Clubl SPEC-89, and the Livermore Fortran Kernels.Measurements demonstrate the potential of r-egister=sensittve modulo schedulers, wh~ch will be useful in evaluating the performance of register-sensitive modrslo scheduling heuristics.

Current compilers for VLIW and superscalar machines increase the instruction level parallelism of an application by merging several basic blocks into an enlarged predicated block, resulting in higher performance code but increased register requirements. We present a framework that computes precisely the interferences among virtual registers in the presence of predicated operations. Graph-coloring biased register allocators can directly use the resulting interference graph. For interval-graph based register allocators, and others, we propose a technique that reduces the register requirements by allowing non-interfering virtual registers that overlap in time to share a common virtual register. Preliminary measurements on a benchmark of loops from the Perfect Club, SPEC-89, and the Livermore Fortran Kernels indicate the effectiveness of this technique.

Modulo scheduling is an efficient technique for exploiting instruction level parallelism in a variety of loops, resulting in high performance code but increased register requirements. We present a set of low computational complexity stage-scheduling heuristics that reduce the register requirements of a given modulo schedule by shifting operations by multiples of II cycles. Measurements on a benchmark suite of 1289 loops from the Perfect Club, SPEC-89, and the Livermore Fortran Kernels shows that our best heuristic achieves on overage 99% of the decrease in register requirements obtained by an optimal stage scheduler.

Aggressive design using level-sensitive latches and wave pipelining has been proposed to meet the increasing need for higher performance digital systems. The optimal clocking problem for such designs has been formulated using an accurate timing model. However, this problem has been difficult to solve because of its nonconvex solution space. The best algorithms to date employ linear programs to solve an overconstrained case that has a convex solution space, yielding suboptimal solutions to the general problem. A new efficient (cubic complexity) algorithm, Gpipe, exploits the geometric characteristics of the full nonconvex solution space to determine the maximum single-phase clocking rate for a closed pipeline with a specified degree of wave pipelining. Introducing or increasing wave pipelining by permanently enabling some latches is also investigated. Sufficient conditions have been found to identify which latches can be removed in this fashion so as to guarantee no decrease and permit a possible increase in the clock rate. Although increasing the degree of wave pipelining can result, in faster clocking, wave pipelining is often avoided in design due to difficulties in stopping and restarting the pipeline under stall conditions without losing data or in reduced rate testing of the circuit. To solve this problem, which has not previously been addressed, we present conditions and implementation methods that insure the stoppability and restartability of a wave pipeline.

A data layout method, array grouping, is proposed to improve communication efficiency and cache utilization of parallel programs containing indirect array references or nonunit stride indexing. Conditions on where to apply this technique are specified in a series of theorems. The technique is then applied to a real finite element application. The experimental results show that communication is reduced by 15%, and data subcache misses by 40% on 56 processors of the KSR1 parallel computer.

We have developed a hierarchical performance bounding methodology that attempts to explain the performance of loop-dominated scientific applications on particular systems. The Kendall Square Research KSR1 is used as a running example. We model the throughput of key hardware units that arc common bottlenecks in concurrent machines. The four units currently used are: memory port, floating-point, instruction issue, and a loop-carried dependence pseudo-unit. We propose a workload characterization, and derive upper bounds on the performance of specific machine-workload pairs. Comparing delivered performance with bounds focuses attention on areas for improvement and indicates how much improvement might be attainable. We delineate a comprehensive approach to modeling and improving application performance on the KSR1. Application of this approach is being automated for the KSR1 with a series of tools including K-MA and K-MACSTAT (which enable the calculation of the MACS hierarchy of performance bounds), K-Trace (which allows parallel code to be instrumented to produce a memory reference trace), and K-Cache (which simulates inter-cache communications based on a memory reference trace).

We have developed an automatic technique for evaluating the communication performance of massively parallel processors (MPPs). Both communication latency and the amount of communication are investigated as a function of a few basic parameters that characterize an application workload. Parameter values are captured in an automatically generated sparse matrix that multiplies a dense vector in the synthetic workload. Our approach is capable of explaining the degradation of processor performance caused by communication.Using the Kendall Square Research KSR1 MPP as a case study, we demonstrate the effectiveness of the technique through a series of experiments used to characterize the communication performance. We show that read and write communciation latencies vary from 150 to 180 and from 80 to 100 processor cycles, respectively. We show that the read communication latency approximates a linear function of the total system communciation (in subpages), write communication approximates a linear function of the number of distinct shared subpages, and that KSR's automatic update feature is effective in reducing the number of read communications given careful binding of threads to processors.

This paper presents an algorithm that allocates registers optimally for straight-line code running on a generic multi-issue computer. On such a machine, an optimal register allocation is one that minimizes the number of issue slots that the code requires. Optimal spill selection and load/store placement are used to minimize the number of additional issue slots needed, given a schedule for the non-memory reference instructions and a fixed number of available physical registers. The generic multi-issue machine model closely models the operation of vector and VLIW processors, and could be extended to model super-scalar processors. The algorithm uses dynamic programming to search the state space of feasible register allocations; implicit and explicit state pruning are used to make the problem tractable without sacrificing optimality. The optimal allocation produced by the algorithm for a substantial example is presented.

Module scheduling is an efficient technique for exploiting instruction level parallelism in a variety of loops, resulting in high performance code but increased register requirements. We present a combined approach that schedules the loop operations for minimum register requirements, given a module reservation table. Our method determines optimal register requirements for machines with finite resources and for general dependence graphs. This method demonstrates the potential of lifetime-sensitive module scheduling and is useful in evaluating the performance of lifetime-sensitive module scheduling heuristics.

Communication has a dominant impact on the performance of massively parallel processors (MPPs). We propose a methodology to evaluate the internode communication performance of MPPs using a controlled set of synthetic workloads. By generating a range of sparse matrices and measuring the performance of a simple parallel algorithm that repeatedly multiplies a sparse matrix by a dense vector, we can determine the relative performance of different communication workloads. Specifiable communication parameters include the number of nodes, the average amount of communication per node, the degree of sharing among the nodes, and the computation-communication ratio. We describe a general procedure for constructing sparse matrices that have these desired communication and computation parameters, and apply a range of these synthetic workloads to evaluate the hierarchical ring interconnection and cache-only memory architecture (COMA) of the Kendall Square Research KSRI MPP. This analysis discusses the impact of the KSRI architecture on communication performance, highlighting the utility and impact of the automatic update feature. It also investigates the impact of system contention on the performance, particularly how it causes potential updates to be ignored.

The MACS performance model introduced here can be applied to a Machine and Application of interest, the Compiler-generated workload, and the Scheduling of the workload by the compiler. The Ma, MAC, and MACS bounds each fix the named subset of M, A, C, and S while freeing the bound from the constraints imposed by the others. A/X performance measurement is used to measure access-only and execute-only code performance. Such hierarchical performance modeling exposes the gaps between the various bounds, the A/X measurements, and the actual performance, thereby focusing performance optimization at the appropriate levels in a systematic and goal-directed manner. A simple, but detailed, case study of the Convex C-240 vector mini-supercomputer illustrates the method.

In this paper, we give an overview of the Cedar multiprocessor and present recent performance results. These include the performance of some computational kernels and the Perfect Benchmarks. We also present a methodology for judging parallel system performance and apply this methodology to Cedar, Cray YMP-8, and Thinking Machines CM-5.

A performance bounding methodology that explains the performance of loop-dominated scientific applications on particular systems is presented. The throughput of key hardware units that are common bottlenecks in concurrent machines is modeled. A workload characterization is proposed, and upper bounds on the performance of specific machine-workload pairs are derived. Comparing delivered performance with bounds focuses attention on areas for improvement and indicates how much improvement might be attainable. A detailed analysis and performance improvement effort for the IBM RS/6000 produced an average lower bound of 1.27 clocks per floating-point operation (CPF), whereas machine peak performance is 0.5 CPF and the V2.01 Fortran compiler attains only 2.43 CPF. Code improvements in this study have achieved 1.36 CPF, increasing the harmonic mean steady-state inner loop performance to 97.6% of the MFLOPS bound. Subsequently, the V2.02 compiler achieved 1.75 CPF, and 1.60 with carefully chosen preprocessing.>

A recently formulated general timing model of synchronous operation is applied to the special case of latch-controlled pipelined circuits. The model accounts for multiphase synchronous clocking, correctly captures the behavior of label-sensitive latches, handles both short- and long-path delays, accommodates wave pipelining, and leads to a comprehensive set of timing constraints. Concurrency of pipeline circuits is defined as a function of the clock schedule and degree of wave pipelining. The authors then identify a special class of clock schedules, coincident multiphase clocks, which provide a lower bound on the value of the optimum cycle time. It is shown that the region of feasible solutions for single-phase clocking can be nonconvex or even disjoint, and a closed-form expression for the minimum cycle time of a restricted but practical form of single-phase clocking is derived. The authors compare these forms of clocking on three pipeline examples and highlight some of the issues in pipeline synchronization.>

Geometric knowledge of the shape of the feasible region formed by pulse width, setup, and hold constraints is used directly by an efficient (cubic complexity) algorithm, Gpipe, to determine the maximum rate for single-phase clocking of a given pipeline. The pipeline model uses level-sensitive latches as synchronizers and can allow wave pipelining. Gpipe is also used to explore the effect of removing nonsynchronizing and/or synchronizing latches on the maximum clock speed of the pipeline. A simple test shows which latches, if any, to remove in order to guarantee no decrease, and permit a possible increase, in the clock rate.>

To enable concurrent instruction execution, scientific computers generally rely on pipelining, which combines with faster system clocks to achieve greater throughput. Each concurrently executing instruction requires buffer space, usually implemented as a register, to receive its result. This paper focuses on the issue of how many registers are required to achieve optimal performance in pipelined scientific computers. Four machine models are considered: single, double, and triple issue scalar machines, and vector machines with various register lengths. A model is presented that accurately relates the register requirements for optimum performance cyclically scheduled loops with tree-dependence graphs to the degree of function unit pipelining, the instruction issue bandwidth, and code properties. A method for finding upper and lower bounds on the minimum register requirements is also presented.The result of this work is a theory for assessing register requirements that can be used to reveal fundamental differences among machines within a space of architectural and implementation design choices. Some experimental data is also provided to support the theory.

article Vector register design for polycyclic vector scheduling Share on Authors: William Mangione-Smith Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, Michigan Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, MichiganView Profile , Santosh G. Abraham Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, Michigan Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, MichiganView Profile , Edward S. Davidson Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, Michigan Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, MichiganView Profile Authors Info & Claims ACM SIGOPS Operating Systems ReviewVolume 25Issue Special IssueApr. 1991 pp 154–163https://doi.org/10.1145/106974.328664Published:01 April 1991 8citation339DownloadsMetricsTotal Citations8Total Downloads339Last 12 Months2Last 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 timing model for circular pipelines is presented and used to obtain the minimum cycle time in terms of circuit delays and clock skews. The model accounts for short- and long-path delays, the effects of clock skew, and the use of both latches and flip-flops as synchronizing elements. The formulation and implementation of algorithms to find the minimum cycle time for both single-phase and a restricted class of multi-phase clocks are described.>

An integrated approach to developing the control software for efficient and dependable manufacturing systems is presented. The formal model of a manufacturing system is used in planning the sequence of operations of each class of jobs to be manufactured by this system. To achieve efficiency, the reservation table technique is used to create optimum cyclic job-shop schedules for processing a batch of jobs. To achieve dependability, a plan-oriented fault detection and correction strategy is proposed.>

The use of the reservation table technique to create optimal cyclic schedules is explored. A detailed discussion and analyses are presented of the properties that determine the theoretical maximum initiation rate, the set of all possible initiation strategies, efficient strategies that yield the maximum realizable performance, and the methods for adding delay to a reservation table so that its maximum realizable rate achieves the theoretical maximum rate. These methods inherently allow multiple devices to be reserved concurrently. They can deal with transport time explicitly. They achieve higher initiation rates by including cycles that involve multiple job initiations. The optimizations are fully valid, not heuristic. These scheduling algorithms can be coupled with the planning environment reported by J.K. Chaar and R.A. Volz (1989). The integrated planning/scheduling framework forms a major component of a software engineering environment that the authors are currently developing.>

This paper studies the impact of the architecture features of the Cray-1 and the Cray X-MP and related compiler optimizations on machine performance. We develop a methodology for evaluating the effectiveness of the Cray Fortran compilers in coping with the architecture features and limitations of the Cray-1 and the Cray X-MP. As examples, the effects of vector register reservation and vector index misalignment on the performance of Livermore Fortran Kernels (LFKs) are presented. The causes of the performance differences of two Cray Fortran compilers, CFT1.14 and CFT77.13, on the vectorized LFKs are described and some areas for further improvement are suggested.

Memory-referencing behavior is analyzed by the study of traces for the purpose of developing local memory structures and management techniques. A trace-processing technique called flattening reduces the dependence of the results on the underlying compiler and architecture on which the trace was generated, and partitions each memory location into its constituent values. The referencing patterns of each value in the resulting trace is described using statistics such as interreference time, lifetime, etc. The referencing patterns of the entire trace are described by histograms showing the distributions for the statistics of the individual values. The results of this analysis indicate that the use of a program-controlled cache to efficiently reduce the traffic from the cache to main memory will improve productivity. By using program control, the future knowledge of the compiler can be imparted to the cache, allowing the rejection of dead values and early replacement of values with long interreference times.>

A paradigm for concurrent computing is explored in which a group of autonomous, asynchronous processes shares a common memory space and cooperates to solve a single problem. The processes synchronize with only a few others at a time; barrier synchronization is not permitted except at the beginning and end of the computation. The paradigm maps directly to a shared-memory multiprocessor with efficient synchronization primitives and is applied to the solution of a large, sparse system of linear equations. The algorithm, called pairwise solve (or PSolve), is presented with several variants to address some of the limitations of previous algorithms. On the Alliant FX/8, PSolve is faster than Gaussian elimination and two common sparse matrix algorithms.>

The nature by which branches and data dependencies generate delays that degrade pipeline performance is investigated in this paper. We show that for the general execution trace, few specific delays can be considered in isolation; rather, the magnitude of any specific delay may depend on the relative proximity of other delays. This phenomenon can make the task of accurately characterizing a trace tape with simple statistics intractable. We present a set of trace reductions that facilitates this task by simplifying the corresponding data-dependency graph. The reductions operate on multiple data-dependency arcs and branches in conjunction; those arcs whose performance implications are redundant with respect to the dependency graph are identified, and eliminated from the graph. We show that the reduced graph can be accurately characterized by simple statistics. We use these statistics to show that as the length of a pipeline increases, the performance degradation due to data dependencies and branches increases monotonically. However, lengthening the pipeline may correspond to decreasing the cycle time of the pipeline. These two opposing effects are used in conjunction to derive an equation for optimal pipeline length for a given trace tape. The optimal pipeline length is shown to be characterized by n = √γα where γ is the ratio of overall circuit delay to latching overhead, and a is a function of the trace statistics that accounts for the delays induced by data dependencies and branches.

High speed scalar processing is an essential characteristic of high performance general purpose computer systems. Highly concurrent execution of scalar code is difficult due to data dependencies and conditional branches. This paper proposes an architectural concept called guarded instructions to reduce the penalty of conditional branches in deeply pipelined processors. A code generation heuristic, the decision tree scheduling technique, reorders instructions in a complex of basic blocks so as to make efficient use of guarded instructions. Performance evaluation of several benchmarks are presented, including a module from the UNIX kernel. Even with these difficult scalar code examples, a speedup of two is achievable by using conventional pipelined uniprocessors augmented by guard instructions, and a speedup of three or more can be achieved using processors with parallel instruction pipelines.

Results are presented on the design, layout, and fabrication of a custom-designed integrated circuit for a residue number system digital filter module. The architecture is based on a ROM-ACCUMULATOR FIR structure in which the modular arithmetic for each modulus is realized on a separate chip. The modules are designed to support error detection and fault isolation at module boundaries. Of the five chips that were fabricated and tested, all were found to be fully operational, with three operating at a maximum data-cycle frequency of approximately 1.7 MHz.

article TIDBITS: speedup via time-delay bit-slicing in ALU design for VLSI technology Share on Authors: Peter Y. T. Hsu Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-Champalgn Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-ChampalgnView Profile , Joseph T. Rahmeh Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-Champalgn Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-ChampalgnView Profile , Edward S. Davidson Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-Champalgn Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-ChampalgnView Profile , Jacob A. Abraham Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-Champalgn Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-ChampalgnView Profile Authors Info & Claims ACM SIGARCH Computer Architecture NewsVolume 13Issue 3June 1985 pp 29–35https://doi.org/10.1145/327070.327121Online:01 June 1985Publication History 5citation474DownloadsMetricsTotal Citations5Total Downloads474Last 12 Months6Last 6 weeks3 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

article Free Access Share on An efficient LISP-execution architecture with a new representation for list structures Authors: Gurindar S. Sohi Coordinated Science Laboratory, University of Illinois, 1101 W. Springfield, Urbana, IL Coordinated Science Laboratory, University of Illinois, 1101 W. Springfield, Urbana, ILView Profile , Edward S. Davidson Coordinated Science Laboratory, University of Illinois, 1101 W. Springfield, Urbana, IL Coordinated Science Laboratory, University of Illinois, 1101 W. Springfield, Urbana, ILView Profile , Janak H. Patel Coordinated Science Laboratory, University of Illinois, 1101 W. Springfield, Urbana, IL Coordinated Science Laboratory, University of Illinois, 1101 W. Springfield, Urbana, ILView Profile Authors Info & Claims ACM SIGARCH Computer Architecture NewsVolume 13Issue 3June 1985 pp 91–98https://doi.org/10.1145/327070.327136Published:01 June 1985Publication History 7citation319DownloadsMetricsTotal Citations7Total Downloads319Last 12 Months17Last 6 weeks3 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Conventional instruction sets or directly interpretable languages (DILs) have not been designed with high-level languages (HLLs) in mind. The modern design problem is to derive a space-time efficient DIL for a HLL processing system. In this paper, we present our approach to the problem of designing well-matched, space-time efficient DILs. A systematic, syntax- and semantics-directed DIL design methodology is presented. It calls for an incremental transformation of the source HLL, until a suitable target DIL is obtained. At the heart of the methodology is a canonic set of language transformations. An experimental study, involving several systematically derived DILs is carried out in order to characterize the relative merits and disadvantages of various sequences of transformations. Various space, time and interpretability trade-offs implied by the transformations are studied.

Shared-cache memory organizations for parallel-pipelined multiple instruction stream processors avoid the cache coherence problem of private caches by sharing single copies of common blocks. A shared cache may have a higher hit ratio, but suffers performance degradation due to access conflicts.

Cache memory organization for parallel-pipelined multiprocessor systems is evaluated. Private caches have a cache coherence problem. A shared cache avoids this problem and can attain a higher hit ratio due to sharing of single copies of common blocks and dynamic allocation of cache space among the processes. However, a shared cache suffers performance degradation due to access conflicts.

Synchronous N-processor systems with M shared memories are considered. Memory interference is modeled for processor request rates between 0 and 1 per memory cycle. Two probability-based models and one queueing-based model are summarized from prior literature. A new steady-state flow model is introduced. This steady-state model is most accurate overall. The queueing model is somewhat more accurate when request rate is near 1, and M and N are large. Accuracy is established with respect to probabilistic simulation. Additional related models are described.

In this paper we compare the performance of virtual memory allocation algorithms. The primary measure of performance is the space-time product of primary memory occupancy, or space-time cost, used by a program during its execution. Using DMIN, an optimal dynamic aliocation algorithm, we compute the minimum space-time cost achievable for some benchmark program runs. We compare the DMIN space-time cost with the space-time cost from: MIN, an optimal static allocation algorithm, VMIN, an optimal variable space algorithm, and two heuristic dynamic allocation algorithms. the page fault frequency algorithm and the damped working set algorithm.

An optimal unrealizable (in real time) virtual memory allocation algorithm DMIN is developed. OMIN has the following properties. A dynamic (time-varying) size of allocation is computed by DMIN to minimize the space-time product of physical memory aliocated to a task during execution. The algorithm is a function of one parameter R, the reactivation time-the average time from the occurrence of a page fault for a task to restarting execution of the task.

A general-purpose multiple-stream processor with shared memory and a single time-multiplexed synchronous bus has been implemented. The AMP-1 system uses eight standard microprocessors and 64K bytes of memory. The design is highly efficient in the use of processor, bus, and memory resources. Preliminary performance measurements agree closely with an analytic memory access conflict model and show extremely low conflict-based performance degradation. Heavy interleaving of the memory and effective multitasking of a job can yield significant performance speedups. Considerations for future implementations are presented.

The memory reference trace of a computation is modeled as a probabilistic process and the information content of that process is derived. Techniques are developed for analyzing the effectiveness of the addressing architecture and Memory/CPU traffic of existing machines with respect to the information theoretic bound for a given trace.

An organization of interleaved multimodule semiconductor memories is studied to facilitate accessing of memory words by a parallel-pipelined processor. All modules are assumed to be identical and to have address cycle (address hold time) and memory cycle of a and c segment time units, respectively. A total of N(=2n) memory modules are arranged such that there are l(=2b) lines for addresses and m(=2n-b) memory modules per line. For a parallel-pipelined processor of order (s,p) which consists of P parallel processors each of which has s degrees of multiprogramming, there can be up to s · p memory requests in each instruction cycle. Memory request collisions are bound to occur in such a system. Performance is evaluated as a function of the memory configuration. Results show that for reasonably large values of N, high performance can be obtained even in the nonbuffered case when l is a · p or more. Buffering has maximum effect on performance when l is near a · p. When l must be grater than a · p for adequate performance in the nonbuffered case, buffering can be used to reduce l while maintaining performance.

A pipeline is defined to be a collection of resources, called segments which can be kept busy simultaneously. A task once initiated, flows from segment to segment for its execution. A collision occurs if two or more tasks attempt to use the same segment at the same time.

A simple, necessary and sufficient test is developed for testing whether a single connection in a tree-type NAND network is redundant. A procedure is presented for testing every connection in the network. The computational complexity of the procedure is mi2 where m = the number of gates and i = the average number of inputs per gate in the network.

A transform that operates on the interconnection topology of a NAND network is presented. The output connecting a designated gate to the network is deleted and is connected instead to a number of other gates in the network. The entire transform may be specified by designating a "transformed gate" and a "modified gate." The new connections are made and the resulting network is then simplified logically by casting out redundancy and merging gates in the network.

Some comments on a recent note for the synthesis of TANT networks are presented. Counter examples that show some defects of the technique are also included.

A branch-and-bound algorithm is presented for the synthesis of multioutput, multilevel, cycle-free NAND networks to realize an arbitrary given set of partially or completely specified combinational switching functions. In a programmed version of the algorithm, fan-in, fan-out, and level constraints may be specified. Cost may be specified as a nonnegative integer linear combination of gates and gate inputs. Further constraints and cost criteria are compatible with the algorithm. A first solution is constructed by a sequence of local decisions, and backtracking is executed to find improved solutions and to prove the optimality of the final solution.

We thank C. H. Haspel for pointing out our error with respect to his packaging procedure. We further basically agree with him as to the trend of logic design toward more logically complex modules. However, we do not share his optimism with regard to the capability of functional decomposition techniques in treating modules of the expected complexity. Rather we envision the evolution of functionally, instead of logically, oriented system design techniques which would perform intermodular design. Intramodular design would then be performed by some such technique as NAND decomposition.

Abstract—The principal synthesis example of Schneider and Dietmeyer's paper [1] is examined by applying a new synthesis algorithm. The minimum NOR gate realization thus obtained is used to illustrate the nonoptimality of their approach and to question their definition of delay. Arguments are advanced for synthesis with simple modules.