There are many scientific and engineering applications that require the resources of a dedicated supercomputer: drug design, weather prediction, simulating vehicle crashes, fluid dynamics simulations of aircraft or even consumer products. Cluster supercomputers can leverage commodity parts with standard interfaces that allow them to be used interchangeably to build supercomputers customized for these and other applications. However, the best design for one application is not necessarily the best design for other applications. Supercomputer design is challenging, but this problem is harder due to the huge range of possible configurations, volatile component availability and pricing, and constraints on available power, cooling, and floor space. Cluster design rules (CDR) is a computer-aided engineering tool that uses resource constraints and application performance models to identify the few best designs among the trillions of designs that could be constructed using parts from a given database. It uses a branch-and-bound strategy based on cluster design principles that can eliminate many inferior designs from the search without evaluating them. For the millions of designs that remain, CDR measures fitness by one of several user-specified application performance models. New application performance models can be added by means of a programming interface. This paper details the concepts and mechanisms inside CDR and shows how it facilitates model-based engineering of custom clusters.

The low cost of clusters built using commodity components has made it possible for many more users to purchase their own supercomputer. However, even modest-sized clusters make significant demands on the power and cooling infrastructure. Minimizing impact of problems after they are detected is not as effective as avoiding problems altogether. This paper is about achieving the best system performance by predicting and avoiding power and cooling problems. Although measuring power and thermal properties of a code is not trivial, the primary issue is making predictions sufficiently in advance so that they can be used to drive predictive, rather than just reactive control at runtime. This paper presents new compiler analysis supporting interprocedural power prediction and a variety of other compiler and runtime technologies making feed-forward control feasible. The techniques apply to most computer systems, but some properties specific to clusters and parallel supercomputing are used where appropriate.

Direct numerical simulation of the Navier-Stokes equations (DNS) is an important technique for the future of computational fluid dynamics (CFD) in engineering applications. However, DNS requires massive computing resources. This paper presents a new approach for implementing high-cost DNS CFD using low-cost cluster hardware. After describing the DNS CFD code DNSTool, the paper focuses on the techniques and tools that we have developed to customize the performance of a cluster implementation of this application. This tuning of system performance involves both recoding of the application and careful engineering of the cluster design. Using the cluster KLAT2 (Kentucky Linux Athlon Testbed 2), while DNSTool cannot match the $0.64 per MFLOPS that KLAT2 achieves on single precision ScaLAPACK, it is very efficient; DNSTool on KLAT2 achieves price/performance of $2.75 per MFLOPS double precision and $1.86 single precision. Further, the code and tools are all, or will soon be, made freely available as full source code.

A method to migrate a task dynamically from a virtual SPMD machine to a virtual SIMD machine is proposed. It is assumed that the SIMD and SPMD virtual machine models only differ to support the different modes of parallelism, and that the program was coded in a mode-independent programming language. The migration procedure does not require the SPMD PEs to be at the same location in the SPMD program at the time of the migration. This work is directly applicable to mixed-mode hybrid SIMDISPMD systems and part of the general problem of task migration in SIMDISPMD mixed-machine heterogeneous systems.

Parallel computers constructed using conventional processors offer the potential to achieve large improvements in execution speed at reasonable cost, however, these machines tend to efficiently implement only coarse-grain MIMD parallelism. To achieve the best possible speedup through parallel execution, a computer must be capable of effectively using all the different types of parallelism that exist in each program. A combination of SIMD, VLIW, and MIMD parallelism, at a variety of granularity levels, exists in most applications; thus, hardware that can support multiple types of parallelism can achieve better performance with a wider range of codes. In this paper, we introduce a new hardware barrier architecture that provides the full DBM functionality we discussed in [11], but can be implemented with much simpler hardware. This mechanism can be used to efficiently support multi-mode moderate-width parallelism with instruction-level granularity (i.e., synchronization cost is approximately one LOAD instruction).

Most programmers spend far more time understanding and modifying existing programs than they spend developing new programs. Current program views used for understanding programs seek to support understanding mainly at the program analysis level; that is, many views are often graphical representations of program analysis concepts, such as the program's data and control dependence graphs, abstract syntax trees or call graphs. However, it may be tedious to understand a program using only such analysis-centered views. We propose a new family of program views that support a more abstract level of program understanding, by describing plan-like program information. In this paper, we show how our views can succinctly present widely-scattered but logically-related program information to describe how certain program effects (e.g. the pattern of occurrence of a global variable) are implemented in a program, and how programmers can interactively manipulate these program views, through view composition and refinement.>

Parallel progrm often exhibit strong preferences for different system structrues, and machines with the ideal structures may all be available within a single heterogeneous network.

In MIMD (Multiple Instructionm Strea, Multiple Data Stream) execution, each processor has its own state.

Features of an explicitly parallel programming language targeted for reconfigurable parallel processing systems, where the machine's N processing elements (PEs) are capable of operating in both the SIMD and SPMD modes of parallelism, are described. The SPMD (single program-multiple data) mode of parallelism is a subset of the MIMD mode where all processors execute the same program. By providing all aspects of the language with an SIMD mode version and an SPMD mode version that are syntactically and semantically equivalent, the language facilitates experimentation with and exploitation of hybrid SIMD/SPMD machines. Language constructs (and their implementations) for data management, data-dependent control-flow, and PE-address-dependent control-flow are presented. These constructs are based on experience gained from programming a parallel machine prototype and are being incorporated into a compiler under development. Much of the research presented is applicable to general SIMD machines and MIMD machines.>

Barrier MIMD's are asynchronous multiple instruction stream, multiple data stream architectures capable of parallel execution of variable execution time instructions and arbitrary control flow (e.g., while loops and calls); however, they differ from conventional MIMD's in that the need for run-time synchronization is significantly reduced. The authors consider the problem of scheduling nested loop structures on a barrier MIMD. The basic approach employs loop coalescing, a technique for transforming a multiply-nested loop into a single loop. Loop coalescing is extended to nested triangular loops, in which inner loop bounds are functions of outer loop indices. In addition, a more efficient scheme to generate the original loop indices from the coalesced index is proposed for the case of constant loop bounds. These results are general, and can be applied to extend previous work using loop coalescing techniques. The authors concentrate on using loop coalescing for scheduling barrier MIMDs, and show how previous work in loop transformations and linear scheduling theory can be applied to this problem.>

Language constructs (and their implementations) for execution mode management and achieving the overlap of control unit and processor operations in an explicitly parallel programming language are described. These are targeted to reconfigurable parallel processing systems, where the machine's processors are capable of operating in both the single-instruction-multiple data (SIMD) and single program-multiple data (SPMD) modes of parallelism. The SPMD mode of parallelism is a subset of the multiple instruction-multiple data (MIMD) mode where all processors execute the same program. By providing all aspects of the language with an SIMD and an SPMD version that are syntactically and semantically equivalent, the language facilitates experimentation with and exploitation of hybrid SIMD/SPMD machines.>

Efficient data layout is an important aspect of the compilation process. A model for the creation of perfect memory maps for large-scale parallel machines capable of user-controlled partitionable single-instruction-multiple data/single-program-multiple data (SIMD/SPMD) operation is developed. The term perfect implies that no memory fragmentation occurs and ensures that the memory map size is kept to a minimum. A major constraint on solving this problem is based on the single program nature of both the SIMD and SPMD modes of parallelism. It is assumed that all processors within the same submachine used identical addresses to access corresponding data items in each of their local memories. Necessary and sufficient conditions are derived for being able to create perfect memory maps, and results are applied to several partitionable interconnection networks.>

In current computer memory system hierarchy, registers and cache are both used to bridge the reference delay gap between the fast processor(s) and the slow main memory. While registers are managed by the compiler using program flow analysis, cache is mainly controlled by hardware without any program understanding. Due to the lack of coordination in managing these two memory structures, significant loss of system performance results because:

A key advantage of SIMD (Single Instruction stream, Multiple Data stream) architectures is that synchronization is effected statically at compile-time, hence the execution-time cost of synchronization between “processes” is essentially zero. VLIW (Very Long Instruction Word) machines are successful in large part because they preserve this property while providing more flexibility in terms of what kinds of operations can be parallelized. In this paper, we propose a new kind of architecture — the “static barrier MIMD” or SBM — which can be viewed as a further generalization of the parallel execution abilities of static synchronization machines.

Pointer and subscripted array references often touch memory locations for which there are several possible aliases; hence these references cannot be made from registers. Although conventional caches can increase performance somewhat, they do not provide many of the benefits of registers, and do not permit the compiler to perform many optimizations associated with register references. The CReg (pronounced 'C-Reg') mechanism combines the hardware structures of cache and registers to create a novel kind of memory structure, which can be used either as processor registers or as a replacement for conventional cache memory. By permitting aliased names to be grouped together. CRegs resolve ambiguous alias problems in hardware, resulting in more efficient execution that even the combination of conventional registers and cache can provide. The authors discuss both the conceptual CReg hardware structure and the compiler analysis and optimization techniques to manage that structure.>