Physics-Informed Neural Networks (PINNs) allow incorporating differential equations to model a system's behavior, and are well able to fit easily differentiable solutions with low-frequency components. They, however, fall short when attempting to learn high-frequency regions or boundary layers. This paper addresses one approach to fixing this by the addition of a Fourier Layer Neural Operator (FNO) to improve accuracy by better fitting regions with high frequency oscillations. We use as an example an underdamped RLC circuit, which resembles that of a boundary layer. The PINN architecture is built to be generalized over other applications, making it a flexible design for further expansion, especially for multiple layers of GPUs.

Technologies such as Multi-Channel DRAM (MCDRAM) or High Bandwidth Memory (HBM) provide significantly more bandwidth than conventional memory. This trend has raised questions about how applications should manage data transfers between levels. This paper focuses on evaluating different usage modes of the MCDRAM in Intel Knights Landing (KNL) manycore processors. We evaluate these usage modes with a sorting kernel and a sorting-based streaming benchmark. We develop a performance model for the benchmark and use experimental evidence to demonstrate the correctness of the model. The model projects near-optimal numbers of copy threads for memory bandwidth bound computations. We demonstrate on KNL up to a 1.9X speedup for sort when the problem does not fit in MCDRAM over an OpenMP GNU sort that does not use MCDRAM.

Summary form only given. The 2008 DARPA Exascale study was one of the first in-depth attempts to project ahead key characteristics for high-end massively parallel systems on the basis of technology trends, architectures, and computational kernels, and identified four major challenges for future systems designs. It focused on a single benchmark, Linpack, and identified two distinct classes of architectures: “heavyweight” and “lightweight.” This talk is a continuation of a series of updates to that study, and includes not only the most recent technology projections but also several new benchmarks for which significant multi-year data exists, and new classes of architectures that have emerged since then. The talk will address changes in characteristics (both before and after the seminal year of 2004 where multi-core took over), and how those characteristics are likely to project into the future. A series of vignettes on specific features will provide insight into areas where current design trends are becoming over or under-balanced. Special attention is given to both computational energy and memory.

The TOP500 is a treasure trove of information on the leading edge of high performance computing. It was used in the 2008 DARPA Exascale technology report to isolate out the effects of architecture and technology on high performance computing, and lay the groundwork to project how current systems might mature through the coming years. Two particular classes of architectures were identified: "heavy-weight" (based on high end commodity microprocessors) and "lightweight," (primarily BlueGene variants), and projections made on performance, concurrency, memory capacity, and power. This paper updates those projections, and adds a third class of "heterogeneous" architectures (leveraging the emerging class of GPU-like chips) to the mix.

Irregular and dynamic applications, such as graph problems and agent-based simulations, often require fine-grained parallelism to achieve good performance. However, current multicore processors only provide architectural support for coarse-grained parallelism, making it necessary to use software-based multithreading environments to effectively implement fine-grained parallelism. Although these software-based environments have demonstrated superior performance over heavyweight, OS-level threads, they are still limited by the significant overhead involved in thread management and synchronization. In order to address this, we propose a Lightweight Chip Multi-Threaded (LCMT) architecture that further exploits thread-level parallelism (TLP) by incorporating direct architectural support for an “unlimited” number of dynamically created lightweight threads with very low thread management and synchronization overhead. The LCMT architecture can be implemented atop a mainstream architecture with minimum extra hardware to leverage existing legacy software environments. We compare the LCMT architecture with a Niagara-like baseline architecture. Our results show up to 1.8X better scalability, 1.91X better performance, and more importantly, 1.74X better performance per watt, using the LCMT architecture for irregular and dynamic benchmarks, when compared to the baseline architecture. The LCMT architecture delivers similar performance to the baseline architecture for regular benchmarks.

This article investigates, via analytic modeling, how a magnetic QCA wire should be organized to provide the highest reliability. We compare a nonredundant wire and two redundant wire organizations. For all three organizations, a fault rate per unit length is used for comparison; additionally, since extra components are necessary to implement the redundant organizations, these components are faulty as well. We show that the difference between these two fault rates is the main driver for selecting a wire organization. Lastly, we develop a guideline for selecting the most reliable wire organization during the circuit design process.

As computing technology delves deeper into the nanoscale regime, reliability is becoming a significant concern, and in response, Teramac-like systems will be the model for many early non-CMOS nanosystems. Engineering systems of this type requires understanding the inherent reliability of both the functional cells and the interconnect used to build the system, and which components are most critical. One particular nanodevice, quantum-dot cellular automata (QCA), offers unique challenges in understanding the reliability of its basic circuits since the device used for logic is also used for interconnect. In this paper, we analyze the reliability properties of two classes of QCA devices: molecular electrostatic-based and magnetic-domain-based. We use an analytic model, probabilistic transfer matrices (PTMs), to compute the inherent reliability of various nontrivial circuits. Additionally, linear regression is used to determine which components are most critical and estimated the reliability gains that may be achieved by improving the reliability of just a critical component. The results show the critical importance of different structures, especially interconnect, as used by the two classes of QCA.

A G4-FET is a 4 gate transistor that combines both JFET and MOS characteristics in a single device that may be fabricated in a standard silicon-on-insulator (SOI) process. In doing so, it enables the conducting channel to be controlled vertically through MOS gates, as well as horizontally, through junction gates. Further, depending upon how it is biased, a single G4-FET can serve as either a not-majority logic gate or as a charge storage-based memory cell. This unique device offers tremendous potential for innovative gate arrays, where real estate can be traded-off between logic and memory functions. In this paper, we take a first look at a mask-programmable G4-FET array that depending upon metal personalization, can function either as a DRAM array or a multiplier.

In this paper, we evaluate the effects of a partitioned global address space (PGAS) versus a flat, randomized distributed global address space (DGAS) in the context of a lightweight multithreaded parallel architecture. We also execute the benchmarks on the Cray MTA-2, a multithreaded architecture with a DGAS mapping. Key results demonstrate that distributing data under the PGAS mapping increases locality, effectively reducing the memory latency and the number of threads needed to achieve a given level of performance. In contrast, the DGAS mapping provides a simpler programming model by eliminating the need to distribute data and, assuming sufficient application parallelism, can achieve similar performance by leveraging large numbers of threads to hide the longer latencies.

Programs with irregular patterns of dynamic data structures and/or those with complicated control structures such as recursion are notoriously difficult to parallelize efficiently. For some highly-irregular applications, such as a SAT solver, it has been nearly impossible to obtain significant parallel speedups on conventional SMP systems over serial implementations. Lightweight multithreading, as found in the Cray MTA and the upcoming XMT (Eldorado), has been demonstrated as an effective approach to attacking these problems. In this paper, we describe a heterogeneous lightweight multithreading that extends ideas found in the Cray machines to support larger numbers of threads while reducing the cost of thread management and synchronization.

No abstract available.

This paper compares the system performance evaluation cooperative (SPEC) Integer and Floating-Point suites to a set of real-world applications for high-performance computing at Sandia National Laboratories. These applications focus on the high-end scientific and engineering domains; however, the techniques presented in this paper are applicable to any application domain. The applications are compared in terms of three memory properties: 1) temporal locality (or reuse over time), 2) spatial locality (or the use of data "near" data that has already been accessed), and 3) data intensiveness (or the number of unique bytes the application accesses). The results show that real-world applications exhibit significantly less spatial locality, often exhibit less temporal locality, and have much larger data sets than the SPEC benchmark suite. They further quantitatively demonstrate the memory properties of real supercomputing applications.

By its nature, MPI leads to coarse grained communications. This is because all current MPI implementations deliver two orders of magnitude more bandwidth for large message sizes (kilobytes) than small message sizes (bytes). This translates into applications that bundle their small communications into larger communications whenever possible. In modern implementations, this sacrifice in the granularity of communication translates directly into a sacrifice in the granularity of synchronization. MPI requires that the entire message arrive before any of the data can be delivered to the application, because message completion is the only synchronization semantic the network can expose to the processor. This paper explores the implications of providing synchronization between the network and the processor at the memory word level using a mechanism such as Full/Empty Bits. This enables the application to begin computing as soon as the data for the first memory referenced has arrived without having to wait for all of the data in the message

This tutorial will explain technologies driving supercomputer speed increases and supercomputers' resulting ability to solve increasingly important problems. In guided session, participants will walk through future supercomputer performance projection on a representative application.Specific topics will include:A review of scientific problems amenable to supercomputers based on the broad-based SCaLeS study. The editor of the SCaLeS report presents this session.The International Technology Roadmap for Semiconductors (ITRS) and its implications for the size, speed, power, and architecture of supercomputers.Current microprocessor-based and emerging "advanced" architectures and their implications on applications performance. There will be special emphasis on the multi-core trend and how applications can use multiple cores effectively.We will discuss the physics issues (speed and power) that will define the end of the current evolutionary trend. We will show how nanotech, reversible logic, and quantum computing may become the basis of a revolutionary change.

Exploring novel computer system designs requires modeling the complex interactions between processor, memory, and network. The Structural Simulation Toolkit (SST) has been developed to explore innovations in both the programming models and hardware implementation of highly concurrent systems. The Toolkit's modular design allows extensive exploration of system parameters while maximizing code reuse and provides an explicit separation of instruction interpretation from microarchitectural timing. This is built upon a high performance hybrid discrete event framework. The SST has modeled a variety of systems, from processor-in-memory to CMP and MPP. It has examined a variety of hardware and software issues in the context of HPC.This poster presents an overview of the SST. Several of its models for processors, memory systems, and networks will be detailed. Its software stack, including support for MPI and OpenMP, will also be covered. Performance results and current directions for the SST will also be shown.

A dramatic trend in computing is the adoption of multi-core technology by the vendors from which our current and future HPC systems are being derived. Multi-core is offered as a path to continued reliance and benefits of Moore's Law while reining in the previously unfettered growth of power consumption and design complexity. Are we saved? or is it but a fools mission, trapping us in a technical cul de sac with no long term direction and no way to reinvent an alternative future. The panel will consider the following questions:* Can multi-core span the next decade of Moore's Law progression?* Are the pins and caches a strangle hold on the future effectiveness of multi-core?* Can innovative algorithmic techniques exploit the opportunities and address the challenges of multi-core?* How will programming models and supporting system software change to accommodate the unique properties and peculiarities of multi-core structures?

Supercomputer architects strive to maximize the performance of scientific applications. Unfortunately, the large, unwieldy nature of most scientific applications has lead to the creation of artificial benchmarks, such as SPEC-FP, for architecture research. Given the impact that these benchmarks have on architecture research, this paper seeks an understanding of how they relate to real-world applications within the Department of Energy. Since the memory system has been found to be a particularly key issue for many applications, the focus of the paper is on the relationship between how the SPEC-FP benchmarks and DOE applications use the memory system. The results indicate that while the SPEC-FP suite is a well balanced suite, supercomputing applications typically demand more from the memory system and must perform more "other work" (in the form of integer computations) along with the floating point operations. The SPEC-FP suite generally demonstrates slightly more temporal locality leading to somewhat lower bandwidth demands. The most striking result is the cumulative difference between the benchmarks and the applications in terms of the requirements to sustain the floating-point operation rate: the DOE applications require significantly more data from main memory (not cache) per FLOP and dramatically more integer instructions per FLOP.

Short vector (SIMD) instructions are useful in signal processing, multimedia, and scientific applications. They offer higher performance, lower energy consumption, and better resource utilization. However, compilers still do not have good support for SIMD instructions, and often the code has to be written manually in assembly language or using compiler builtin functions. Also, in some applications, higher parallelism could be achieved if compilers inserted permutation instructions that reorder the data in registers. In this paper we describe how we create SIMD instructions from regular code, and determine ordering of individual operations in the SIMD instructions to minimize the number of permutation instructions. Individual memory operations are grouped into SIMD operations based on their effective addresses. The SIMD data flow graph is then constructed by following data dependences from SIMD memory operations. Then, the orderings of operations are propagated from SIMD memory operations into the graph.We also describe our approach to compute decomposition of a given permutation into the permutation instructions of the target architecture. Experiments with our prototype compiler show that this approach scales well with the number of operations in SIMD instructions (SIMD width) and can be used to compile a number of important kernels, achieving up to 35% speedup.

This paper presents the Quantum-Dot Cellular Automata (QCA) physical design problem, in the context of the VLSI physical design problem. The problem is divided into three subproblems: partitioning, placement, and routing of QCA circuits. This paper presents an ILP formulation and heuristic solution to the partitioning problem, and compares the two sets of results. Additionally, we compare a human-generated circuit to the ILP and Heuristic solutions. The results demonstrate that the heuristic is a practical method of reducing partitioning run time while providing a result that is close to the optimal for a given circuit.

This paper details nano-scale devices being researched by physical scientists to build computational systems. It also reviews some existing system design work that uses the devices to be discussed. It concludes with a discussion of how the authors believe system-level research can best be used to positively affect actual device development. This work has led to a more thorough design methodology that address whether or not computationally interesting and buildable circuits are possible with the quantum-dot cellular automata (QCA), while also providing significant wins over end-of-the-roadmap CMOS.

Chip level multithreading is growing in use throughout the microprocessor world as evidenced in the Intel Pentium 4 and the upcoming innovations in the POWER architecture. These processors typically use a few coarse grain threads that can be difficult for the programmer or compiler to exploit; however, Processing in Memory (PIM) is a technology that has been explored through a long series of supercomputer projects as a facilitator for a different multithreaded execution models. In the multithreading model explored by PIMs, the threads can have radically different characteristics. Specifically, PIMs seek to exploit a large number of very fine grained threads to hide memory access latency and increase parallelism. PIM supports these small threads, or "threadlets", by providing a fast hardware synchronization mechanism, support for harware managment of creation and destruction of threads, and a "shared register" approach which extends the shared memory thread model. This paper discusses some analysis of some very large scientific codes in terms of how they might be mapped onto such a multithreading model with a focus on extremely fine grain threads.

One of the major design decisions when developing a new microprocessor is determining the target pipeline depth and clock rate since both factors interact closely with one another. The optimal pipeline depth of a processor has been studied before, but the impact of the memory system on pipeline performance has received less attention. This study analyzes the affect of different level-1 cache designs across a range of pipeline depths to determine what role the memory system design plays in choosing a clock rate and pipeline depth for a microprocessor. The pipeline depths studied here range from those found in current processors to those predicted for future processors. For each pipeline depth a variety of level-1 cache sizes are simulated to explore the relationship between clock rate, pipeline depth, cache size and access latency. Results show that the larger caches afforded by shorter pipelines with slower clocks outperform longer pipelines with smaller caches and higher clock rates.

Memory may be the only system component that is more commoditized than a microprocessor. To simultaneously exploit this and address the impending memory wall, processing in memory (PIM) research efforts are considering ways to move processing into memory without significantly increasing the cost of the memory. As such, PIM devices may become the basis for future commodity clusters. Although these PIM devices may leverage new computational paradigms such as hardware support for multi-threading and traveling threads, they must provide support for legacy programming models if they are to supplant commodity clusters. This paper presents a prototype implementation of MPI over a traveling thread mechanism called parcels. A performance analysis indicates that the direct hardware support of a traveling thread model can lead to an efficient, lightweight MPI implementation.

We are all aware of the memory wall and the deleterious effects of bandwidth and latency limitations on performance. We also watch with some degree of amazement at the relentless march of Moore's Law as ever-larger numbers of transistors are used in increasingly clever architectural and microarchitectural techniques to attempt to reduce the effects of the wall. What have not risen to the same level of consciousness, however, are the effects that all of this has on the size of program state and our ability to manipulate it, and move it, to avoid the wall. Instead, the Law of Unintended Consequences has left us with heavier and heavier state, which in turn condemns them to continued existence in the bowels of bigger and bigger microprocessor chips, and farther and farther away from the data they seek in memory. This talk is a plea to architects to reconsider what we have been doing to ourselves, and ask if there are alternatives that have been overlooked. The talk will begin by revisiting the notion of state, and plot its explosive growth over the last 30 years. The key points of expansion will be correlated with architectural and microarchitectural advances. Then we will walk through some observations gained from exploring designing in some emerging technologies, and ask the question of what alternative execution models, particularly premised on light weight states, might do to increase performance and reduce complexity.

The out-of-order issue queue (IQ), used in modern superscalar processors is a considerable source of energy dissipation. We consider design alternatives that result in significant reductions in the power dissipation of the IQ (by as much as 75%) through the use of comparators that dissipate energy mainly on a tag match, 0-B encoding of operands to imply the presence of bytes with all zeros and, bitline segmentation. Our results are validated by the execution of SPEC 95 benchmarks on a true hardware level, cycle-by-cycle simulator for a superscalar processor and SPICE measurements for actual layouts of the IQ in a 0.18-/spl mu/m CMOS process.

Hybrid technology multithreaded architecture (HTMT) is an ambitious new architecture combining cutting edge technologies to reach petaflop performance sooner than current technology trends allow. It is a massively parallel architecture with multi-threaded hardware and a multi-level memory hierarchy. Microservers provide a new perspective for viewing this memory hierarchy whereby memory is actively involved in process execution. This paper discusses the microserver memory semantics and initial HTMT execution models to analyze application at each level of the system hierarchy and to develop user-level functions for expressing this inherent concurrency and parallelism. In order to do this we studied several applications to model the control and data flow within the HTMT hierarchy and developed pseudo-code representing the user-level functions necessary to express application concurrency and parallelism.

Pipelining is a technique that has long since been considered fundamental by computer architects. However, the world of nanoelectronics is pushing the idea of pipelining to new and lower levels — particularly the device level. How this affects circuits and the relationship between their timing, architecture, and design will be studied in the context of an inherently self-latching nanotechnology termed Quantum Cellular Automata (QCA). Results indicate that this nanotechnology offers the potential for “free” multi-threading and “processing-in-wire”. All of this could be accomplished in a technology that could be almost three orders of magnitude denser than an equivalent design fabricated in a process at the end of the CMOS curve.

The instruction dispatch buffer (DB, also known as an issue queue) used in modem superscalar processors is a considerable source of energy dissipation. We consider design alternatives that result in significant reductions in the power dissipation of the DB (by as much as 60%) through the use of: (a) fast comparators that dissipate energy mainly on a tag match, (b) zero byte encoding of operands to imply the presence of bytes with all zeros and, (c) bitline segmentation. Our results are validated by the execution of SPEC 95 benchmarks on true hardware level, cycle-by-cycle simulator for a superscalar processor and SPICE measurements for actual layouts of the DB and its variants in a 0.5 micron CMOS process.

In recent years, reducing power has become an important design goal for high-performance microprocessors. This work attempts to bring the power issue to the earliest phases of microprocessor development, in particular, the stage of defining a chip microarchitecture. We investigate power-optimization techniques of superscalar microprocessors at the microarchitecture level that do not compromise performance. First, major targets for power reduction are identified within microarchitecture, where power is heavily consumed or will be heavily consumed in next-generation superscalar processors. Then, a new, energy-efficient version of a multicluster microarchitecture is developed that reduces energy the identified critical design points with minimal performance impact. A methodology is developed for energy-performance optimization at the microarchitecture level that generates, for a microarchitecture, a set of energy-efficient configurations, forming a convex hull in the power-performance space. Detailed simulation of the baseline and proposed multicluster architectures has been performed using the developed optimization methodology. A comparison of the two microarchitectures, both optimized for energy efficiency, shows that the multicluster architecture is potentially up to twice as energy efficient for wide issue processors, with an advantage that Grows with the issue width. Conversely, at the same power dissipation level, the multicluster architecture supports configurations with measurably higher performance than equivalent conventional designs.

Despite the seemingly endless upw ards spiral of modern VLSI technology, many experts are predicting a hard w all for CMOS in about a decade. Given this, researc hers con tin ue to look at alternative technologies, one of which is based on quan tumdots, called quan tumcellular automata (QCA). While the first such devices have been fabricated, little is kno wn about how to design complete systems of them. This paper summarizes one of the first such studies, namely an attempt to design a complete, albeit simple, CPU in the technology. T o design a theoretical QCA microprocessor, two things must be accomplished. First a device model of the processor must be constructed (i.e. the schematic itself). Second, methods for sim ulatingand testing QCA designs m ust be developed. This paper summarizes the beginnings of a simple QCA microprocessor (namely, its dataflow) and a QCA design and simulation tool.

In recent years reducing power has become a critical design goal for high-performance microprocessors. This work attempts to bring the power issue to the earliest phase of high-performance microprocessor development. We propose a methodology for power-optimization at the micro-architectural level. First, major targets for power reduction are identified within superscalar microarchitecture, then an optimization of a superscalar micro-architecture is performed that generates a set of energy-efficient configurations forming a convex hull in the power-performance space. The energy-efficient families are then compared to find configurations that dissipate the lowest power given a performance target, or, conversely, deliver the highest performance given a power budget. Application of the developed methodology to a superscalar micro-architecture shows that at the architectural level there is a potential for reducing power up to 50%, given a performance requirement, and for up to 15% performance improvement, given a power budget.

Despite the seemingly endless upwards spiral of modern VLSI technology many experts are predicting a hard wall for CMOS in about a decade. Given this, researchers continue to look at alternative technologies, one of which is based on quantum dots, called quantum cellular automata. While the first such devices have been fabricated, little is known about how to design complete systems. This paper summarizes one of the first such studies, namely an attempt to design a complete, albeit simple, CPU in the technology. The projections are striking: a projected 10 to 1 increase in circuit density when compared to a CMOS equivalent, but a design approach which is radically different from conventional "logic" design, especially in timing considerations.

Article Microservers: a new memory semantics for massively parallel computing Share on Authors: Jay B. Brockman Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, INView Profile , Peter M. Kogge Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, INView Profile , Thomas L. Sterling Center for Advanced Computing Research, California Institute of Technology, Pasadena, CA Center for Advanced Computing Research, California Institute of Technology, Pasadena, CAView Profile , Vincent W. Freeh Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, INView Profile , Shannon K. Kuntz Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, INView Profile Authors Info & Claims ICS '99: Proceedings of the 13th international conference on SupercomputingJune 1999 Pages 454–463https://doi.org/10.1145/305138.305234Online:01 May 1999Publication History 29citation567DownloadsMetricsTotal Citations29Total Downloads567Last 12 Months9Last 6 weeks1 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

Processing-in-memory (PIM) chips that integrate processor logic into memory devices offer a new opportunity for bridging the growing gap between processor and memory speeds, especially for applications with high memory-bandwidth requirements.The Data-IntensiVe Architecture (DIVA) system combines PIM memories with one or more external host processors and a PIM-to-PIM interconnect.DIVA increases memory bandwidth through two mechanisms: (1) performing selected computation in memory, reducing the quantity of data transferred across the processor-memory interface; and (2) providing communication mechanisms called parcels for moving both data and computation throughout memory, further bypassing the processor-memory bus.DIVA uniquely supports acceleration of important irregular applications, including sparse-matrix and pointer-based computations.In this paper, we focus on several aspects of DIVA designed to effectively support such computations at very high performance levels: (1) the memory model and parcel definitions; (2) the PIM-to-PIM interconnect; and, (3) requirements for the processor-to-memory interface.We demonstrate the potential of PIMbased architectures in accelerating the performance of three irregular computations, sparse conjugate gradient, a natural-join database operation and an object-oriented database query.

In this paper, we use the recently developed static transition diagram technique to derive analytical formulas expressing latch power in terms of true and spurious switching activities at the data input. These formulas are verified through analog simulation and applied to a number of commonly used latch designs. The derived model will allow designers to substitute parameters of true and spurious switching activities into analytical formulas for quickly obtaining accurate latch power and then select latches which have the best power-dissipation characteristics for those parameter values.

Register files (RF) represent a substantial portion of the energy budget in modern processors, and are growing rapidly with the trend towards wider instruction issue. The actual access energy costs depend greatly on the register file circuitry used. This paper compares various RF circuitry techniques for their energy ef- ficiencies, as a function of architectural parameters such as the number of registers and the number of ports. The Port Priority Selection technique was found to be the most energy efficient. The dependence of register file access energy upon technology scaling is also studied. However, as this paper shows, it appears that none of these will be enough to prevent centralized register files from becoming the dominant power component of next-generation superscalar computers, and alternative methods for inter-instruction communication need to be developed. Split register file architecture is analyzed as a possible alternative.

The EXECUBE chip is a new single part type building block for MPP systems that scales seamlessly from a few chips (with a few hundred mips) to thousands of chips with petaop potential. Further, the chip architecture supports directly both SIMD and MIMD modes of processing, permitting not only the best of both current parallel computing modes but also new modes not possible with more conventional designs. This paper discusses the overall architecture of the EXECUBE chip, the new computational model it represents, some comparisons against the current state of the art, how it might be used for real applications, and some extrapolations into future developments.

An m thorder recurrence problem is defined as the computation of X1, . . . XN, where Xi=f (ai, Xi-1, . . Xi-m) and ai is a set of parameters. On a pipelined computer, where the total stage delay in computing f is df time units, the solution output rate is one new Xi each df time unit. This paper describes a method for increasing this rate to 1 per time unit when the function f has certain simple functional properties. The total stage delay and complexity of the resulting pipelines are also described.

An mth-order recurrence problem is defined as the computation of the series x1, x2, ..., XN, where xi= fi(xi-1, ..., xi-m) for some function fi. This paper uses a technique called recursive doubling in an algorithm for solving a large class of recurrence problems on parallel computers such as the Iliac IV. Recursive doubling involves the splitting of the computation of a function into two equally complex subfunctions whose evaluation can be performed simultaneously in two separate processors. Successive splitting of each of these subfunctions spreads the computation over more processors. This algorithm can be applied to any recurrence equation of the form xi= f(bi, g(ai, xi-1)) where f and g are functions that satisfy certain distributive and associative-like properties. Although this recurrence is first order, all linear mth-order recurrence equations can be cast into this form. Suitable applications include linear recurrence equations, polynomial evaluation, several nonlinear problems, the determination of the maximum or minimum of N numbers, and the solution of tridiagonal linear equations. The resulting algorithm computes the entire series x1, ..., xNin time proportional to [log2N] on a computer with N-fold parallelism. On a serial computer, computation time is proportional to N.