The major challenge to Exaflop computing, and more generally, efficient high-end computing, is in finding the best “matches” between advanced hardware capabilities and the software used to program applications, so that top performance will be achieved. Several benchmarks show very disappointing performance progress over the last decade, clearly indicating a mismatch between hardware and software. To remedy this problem, it is important that key performance enablers at the software level-autotuning, performance analysis tools, full application optimization-are understood. For each area, we highlight major limitations and most promising approaches to reaching better performance and energy levels. Finally, we conclude by analyzing hardware and software design, trying to pave the way for more tightly integrated hardware and software codesign.

This paper presents an empirical approach to measuring and modeling the energy consumption of multicore processors.The modeling approach allows us to find a breakdown of the energy consumption among a set of key hardware components, also called HW nodes. We explicitly model the front-end and the back-end in terms of the number of instructions executed. We also model the L1, L2 and L3 caches. Furthermore, we explicitly model the static and dynamic energy consumed by the the uncore and core components. From a software perspective, our methodology allows us to correlate energy to the executed code, which helps find opportunities for code optimization and tuning.

Summary form only given. Energy/performance results for parallel (and sequential) computing are still, usually hard to predict and often disappointing. A model using invariant-based equations is being applied to predict energy/performance as HW and SW are changed in codesign studies. The physical model consists of HW nodes chosen to match architectural issues, together with automatically extracted SW codelets that are easy to measure and model. HW/SW measurements of computational capacity (BW used) and power [based on HW counters and SW modification (Decan)] are used by the Cape tool to evaluate tradeoffs quickly and find optimal solutions to various codesign problems. Codelets from a number of real applications are being analyzed and modeled.

Building HPC systems from small, cost/effective production nodes has been a favored engineering approach for many years. Technology has driven a variety of solutions over time. Today, commodity SMP nodes and interconnection networks, together with highly evolved programming models and parallel software engineering tools make a compelling combination. An overview of these topics will be presented, together with some specific solution examples. Open problems and issues will be discussed.

No abstract available.

In this paper, we describe a methodology for analysis and improvement of computer systems through comparative evaluation, and Newton, a prototype implementation of this methodology. Newton aids its users in identifying and understanding the keys to performance of existing computer systems by finding characteristics which differentiate the performance of any given pair of systems. Newton collects information about a computer, builds a model which allocates the running time of program segments (e.g. loops and basic blocks) to various hardware and software components of the system, highlights differences between multiple systems by comparing the measured data and model, and predicts what performance improvement will result if a discovered bottleneck is alleviated from the system.>

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.

In the past three years, the Perfect BenchmarkTM Suite has evolved from a supercomputer performance evaluation plan, presented by Kuck and Sameh at the 1987 International Conference on Supercomputing, to a vigorous international activity. This paper surveys the current state of this supercomputer performance evaluation effort with particular focus on the adopted methodology. While there has been considerable success in achieving the goals of the plan, some issues remain unresolved, and new questions have surfaced.

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.>

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.

Previous models of program speedup on parallel architectures tend to ignore I/O activity and other important issues. In this paper we derive analytic speedup models including I/O activities. We show that ignoring I/O yields conservative speedup results. We explore the effectiveness of using hardware format conversion units in multiprocessors [33]. We prove that hardware parallel format conversion loses its edge over software parallel format conversion if the ratio of the number of processors to I/O bandwidth increases. For a given number of processors, program speedup is more sensitive to the available I/O bandwidth rather than the format conversion speed. Ninety-one Fortran programs are used in various experiments to verify our models and conclusions. Most of the programs are I/O bound. Our empirical results show that including I/O activity improves the speedup factor for 78 percent of the programs, and 18 percent of the programs are sped up only due to faster I/O activities. For a serial machine, using hardware format conversion units designed in [13] reduces program execution time by an average factor of three. The software format conversion speed used is obtained from direct measurements on an IBM 4341 running CMS and a CDC Cyber 175 running NOS. For multiprocessor systems a factor of eight increase in the processors to I/O bandwidth ratio reduces the effectiveness of hardware format conversion to an average factor of 1.36.

The feasibility of automatic restructuring of nonnumerical programs for parallel processing is studied through experiments using Parafrase, an automatic restructurer at the University of Illinois, Urbana-Champaign. Parallel processing speedup results due to automatic restructuring for several basic nonnumerical problems are presented. The loops encountered are classified at a low level. On the basis of the speedup results and the analyses of the loop types, the difficulty and the effectiveness of automatic restructuring are discussed. The experiments suggest that automatic restructuring can be a useful tool for exploiting parallelism in the sequential form of nonnumerical programs.

This paper presents the design of a relational query processor. The query processor consists of only four processing PIPEs and a number of random-access memory modules. Each PIPE processes tuples of relations in a bit-serial, tuple-parallel manner for each of the primitive database operations which comprise a complex relational query. The design of the query processor meets three major objectives: the query processor must be manufacturable using existing and near-term LSI (VLSI) technology; it must support in a uniform manner both the numeric and nonnumeric processing requirements a high-level user interface like SQL presents; and it must support the query-processing strategy derived in the query optimizer to satisfy certain system-wide performance optimality criteria.

The Burroughs Scientific Processor (BSP), a high-performance computer system, performed the Department of Energy LLL loops at roughly the speed of the CRAY-1. The BSP combined parallelism and pipelining, performing memory-to-memory operations. Seventeen memory units and two crossbar switch data alignment networks provided conflict-free access to most indexed arrays. Fast linear recurrence algorithms provided good performance on constructs that some machines execute serially. A system manager computer ran the operating system and a vectorizing Fortran compiler. An MOS file memory system served as a high bandwidth secondary memory.

Dependence graphs can be used as a vehicle for formulating and implementing compiler optimizations. This paper defines such graphs and discusses two kinds of transformations. The first are simple rewriting transformations that remove dependence arcs. The second are abstraction transformations that deal more globally with a dependence graph. These transformations have been implemented and applied to several different types of high-speed architectures.

It is possible to improve the paging performance of a program by applying transformations to the source program that improve data access locality. We discuss this subject in general terms, including automation of these transformations, and present a number of such transforms. This is followed by experimental results which indicate that these transformations are indeed effective. Use of practical, simple memory management policies like the fixed allocation local lru replacement algorithm leads to average improvements over untransformed programs of a factor of 10 in space-time cost, and a factor of 5 in memory size. Multiprogramming questions are also discussed.

A design automation system for the design of digital systems from a high-level algorithmic description is proposed. The definition of the data-dependence graph and techniques for performing transformations that lead to optimization of hardware are described. The system can be used on several levels of design with the VLSI layout level given particular emphasis.

The purpose of this paper is to present some ideas on multiprocessor design and on automatic translation of sequential programs into parallel programs for multiprocessors. With respect to machine design, two subjects are discussed. First, a multiprocessor allowing parallelism at a very low level is sketched and then, a brief discussion on the interconnection network is presented.

The main goal of this paper is to show that a large number of processors can be used effectively to speed up simple Fortran-like loops consisting of assignment statements. A practical method is given by which one can check whether or not a statement is dependent upon another. The dependence structure of the whole loop may be of different types. For each type, a set of time and processor upper bounds is given. We also show how a loop can sometimes be transformed to change its dependence structure. Finally, we give a result on the possible splitting up of a given recurrence system into a number of smaller subsystems. These results can be used to modify and sometimes improve the bounds for the loops as demanded by special circumstances.

In this paper three stable parallel algorithms for solving dense and tndlagonai systems of lmear equations are discussed The algorithms are based on Givens' reduction of a matrix to the upper triangular form The algorithm for the dense case requires O(n) time steps compared to O(n log n) steps for Gausslan ehmmatlon with pivoting (in the absence of certain features of machine logic and hardware) For the trldlagonal case, one of the algorithms presented here is superior to the best previous algorithm in that with a modest increase in time It does not fall if any of the leading pnnclpal submatrlces is singular, the probablhty of over-or underflow is minimized, and the error bound does not grow exponentially Furthermore, it is most statable when only a hmtted number of processors ts available.

article Free Access Share on Practical Parallel Band Triangular System Solvers Authors: S. C. Chen Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, ILView Profile , D. J. Kuck Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, ILView Profile , A. H. Sameh Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, ILView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 4Issue 3Sept. 1978 pp 270–277https://doi.org/10.1145/355791.355797Published:01 September 1978Publication History 80citation447DownloadsMetricsTotal Citations80Total Downloads447Last 12 Months20Last 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

The object of this paper is to bring together several models of interleaved or parallel memory systems and to expose some of the underlying assumptions about the address streams in each model. We derive the performance for each model, either analytically or by simulation, and discuss why it yields better or worse performance than other models (e.g., because of dependencies in the address stream or hardware queues, etc.). We also show that the performance of a properly designed system can be a linear rather than a square root function of the number of memories and processors.

New results are given concerning the design of combinational logic circuits. We give time and component bounds for combinational circuits specified in several ways. For any sequential machine defined by linear recurrence relations, we discuss an algorithm for the synthesis of equivalent combinational logic. The procedure includes upper bounds on the time and components involved. We also discuss the transformation of nonlinear recurrences into combinational circuits. Examples are given using gates as well as IC's as components. These include binary addition, multiplication, and ones' position counting. The time and component bounds our procedure yields compare favorably with traditional results.

The error properties of floating-point arithmetic using various rounding methods (including ROM rounding, a new scheme) are analyzed. Guard digits are explained, and the rounding schemes' effectiveness are evaluated and compared.

We show that if the size of the tridiagonal matrix in any given iteration is n, then the parallel QR algorithm requires 0(log2n) steps with 0(n) processors per iteration and no square roots. This results in a speedup of 0(n/log2n) over the sequential algorithm with an efficiency of 0(1/log2n). We also give an error analysis of the parallel triangular system solvers used in each iteration.

A framework for the study of computer capacity is given by means of a definition of capacity in terms of speeds of various parts of a computer as well as memory size. In addition to these machine parameters, we also include certain parameters of the programs to be run on a given machine. The calculation of theoretical capacity is given for several combinations of processor, memory, and I/O bandwidth for overlapped machines. The tradeoff between primary memory size and I/O bandwidth is discussed in terms of the new definition.

ROM-rounding is introduced and is shown to compare favorably with existing floating-point rounding methods on design considerations and on performance over a series of error tests. The error-retarding value of guard digits, of rounding the aligned operand, and of rounding in general are discussed.

This paper presents a number of bounds on the parallel processor evaluation of arithmetic expressions. Several previous papers show that if the evaluation of an expression using a serial computer requires t operations, by using a number of processors in parallel, the expression may be evaluated in time proportional to $\log _2 t$. Since $\log _2 t$ is an obvious lower bound, it is of interest to attempt to approach this bound. The present paper shows that if more information than the number of operations (or operands) is known, sharper bounds may be given in certain cases. Thus if the number of parenthesis pairs is small or if the depth of parenthesis nesting is small, we may approach the lower bound. A new bound is also given for expressions which have few division operations. Similarly, if the expression’s form is restricted, sharper bounds may be found. Thus generalizations of polynomials and generalizations of continued fractions are shown to have improved bounds. We also give a new bound for expressions without division operations which have a limited number of parenthesis pairs. Finally, we give an upper bound on the time to evaluate expressions in which multiplication is not commutative.

We give new time and processor bounds for the parallel evaluation of linear recurrence systems. Such systems may be represented as x̄ =c̄ + Ax̄ where A is an n X n strictly lower triangular matrix and c is a constant column vector. We show that O og22n) time steps and n3/ 8 + 0O2) processors are sufficient. We also show that mth order linear recurrences, i. e., where A has a bandwidth of m, can be computed within O(log2mlog2n) time steps with at most 3m2n/4 + O(mn) processors. In all cases, our bounds on time and processors are improvements on previous results, and the computer need only perform one type of operation at each time step (SIMD operation). By a simple transformation, the results can also be applied to the solution of any triangular linear system of equations Ax̄ = b̄.

This paper is concerned with the problem of analyzing ordinary Fortran-like programs to determine how many of their operations could be performed simultaneously. Algorithms are presented for handling arithmetic assignment statements, DO loops and IF statement trees. The height of the parse trees of arithmetic expressions is reduced by distribution of multiplication over addition as well as the use of associativity and commutativity. DO loops are analyzed in terms of their index sets and subscript forms. Some general underlying assumptions about machine organization are also given. In terms of several measures which are defined, the results of experimental analyses are presented. About 20 Fortran IV programs consisting of nearly 1000 source cards were analyzed. Evidence is given that for very simple Fortran programs 16 processors could be effectively used operating simultaneously in a parallel or pipeline fashion. Thus, for medium or large size Fortran programs, machines consisting of multiples of a basic 16 processor unit could be used.

The fastest parallel and pipeline computers presently being designed use interleaved memory systems with more than 16 individual memory units. A common difficulty in these machines is the alignment of data before it is arithmetically processed. Usually the arithmetic unit is used to preprocess the data. This may increase the computation time by a factor of two or more. This paper proposes a programmed memory preprocessing system which aligns the data before it is passed to the arithmetic processor.

Abstract—The structure of ILLIAC IV, a parallel-array computer containing 256 processing elements, is described. Special features include multiarray processing, multiprecision arithmetic, and fast data-routing interconnections. Individual processing elements execute 4×106instructions per second to yield an effective rate of 109 operations per second.

For more than fifteen years, people have been talking and writing about the possibility of chess playing programs. Previous "successful" programs have played a scaled-down game, parts of the game, or a weak overall game. This paper describes the first chess program to play a creditable amateur tournament game; it won the class D trophy in a Massachusetts State Chess Association Amateur Tournament. The paper is a well-written case study in artificial intelligence.

Abstract—An overview of the ILLIAC IV system is given and its software plans are discussed.