Manycore architectures are a promising direction for single-chip performance. They typically use in-order cores and caches as building blocks and can produce good performance on regular applications. However, on irregular applications, they have low core utilization due to data-dependent control-flow and memory access.

Traditional supercomputers have focused on dense computation performance as exemplified by HPL. Graph processing applications differ with extreme irregularity ($10^{9}$imbalance in skewed, real-world graphs) that produces unpredictable work, parallelism, memory access, and communication. Together, these make scalable performance and programming difficult. We describe the UpDown system architecture, co-designed for irregular graph computations. UpDown provides efficient fine-grained thread invocations ($\sim$10 instructions), direct messaging (no network interface card) for scalable local and global messaging, and split-transaction memory operations that enable extremely high memory bandwidth. Combined with architectural support for global addressing and an aggressive network design, these UpDown features enable direct exploitation of edge and vertex parallelism, using it to deliver breakthrough graph processing performance and programmability. We evaluate the performance of the UpDown system using a challenging suite of graph applications (Pagerank, Breadth-first Search, Triangle Counting, Partial Match, etc). For a single-node, results show 100-fold performance advantage over multicore CPUs. Compared to today's fastest scalable parallel computers UpDown achieves 1000-fold performance increases. UpDown delivers these levels of performance with high-level programmability, these programs directly express vertex-edge parallelism which UpDown exploits directly in hardware.

Datacenter growth is constrained by power grids because the constant power required by datacenters (DCs) is difficult to balance with variable solar and wind generation. DC load flexibility is the key to solving these grid problems, but it conflicts with the stable capacity needed for compute efficiency.

The rapid growth of cloud datacenters has raised concerns about impact on both environment and power grids. Datacenter flexibility—adjusting power load in response to carbon intensity, power prices, and excess generation—offers a promising solution. But externally determined capacity variation degrades datacenter capacity and cloud scheduler performance. We characterize this degradation on commercial and synthetic workloads, showing goodput losses of up to 19-24%. Goodput loss stems from job terminations caused by capacity losses, particularly impacting long-running jobs, such as continuous cloud VMs.

Conventional Function-as-a-Service (FaaS) systems provide limited support for the applications to configure FaaS deployments for performance needs, limiting the FaaS applicability and productivity. Recent work addresses these limitations by introducing a performance abstraction, which allows applications to specify their performance needs through predefined Software-level Agreements (SLAs). FaaS systems then use these SLAs to manage resources and scheduling, guaranteeing application performance.

Processor datapaths grew from 4 to 512 bits via Single-Instruction-Multiple-Data (SIMD) parallelism. SIMD applies the same operation to multiple values, which increases performance and reduces the instruction count. However, these evolvements do not provide support for variable-width values, so programmers ‘pad’ values to align to outliers, wasting the upper bits with zeros in both registers and datapath. We propose VarVE, a vector instruction set extension built upon the state-of-the-art vector-length agnostic SIMD instruction set: ARM SVE. VarVE provides native support for variable-width values within a vector, avoiding padding waste, thus making better use of the SIMD datapath. VarVE's design enables a flexible strip mining model with a variety of optimizations. Evaluation of VarVE shows 60x speedup over ARM in kernels with element packing and unpacking, and 1.3x - 5.4x speedup over SVE for pure-compute filtering in TPC-H benchmarks. VarVE also achieves 2x speedup on a neural network inference task. All these results exemplify VarVE's general ability to improve datapath and memory system efficiency.

Stream Processing Engines (SPEs) traditionally de-ploy applications on a set of shared workers (e.g., threads, processes, or containers) requiring complex performance man-agement by SPEs and application developers. We explore a new approach that replaces workers with Rate-based Abstract Ma-chines (RBAMs). This allows SPEs to translate stream operations into FaaS invocations, and exploit guaranteed invocation rates to manage performance. This approach enables SPE applications to achieve transparent and predictable performance. We realize the approach in the Storm-RTS system. Exploring 36 stream processing scenarios over 5 different hardware config-urations, we demonstrate several key advantages. First, Storm-RTS provides stable application performance and can enable flexible reconfiguration across cloud resource configurations. Sec-ond, SPEs built on RBAM can be resource-efficient and scalable. Finally, Storm-RTS allows the stream-processing paradigm to be extended from the cloud to the edge, using its performance stability to hide edge heterogeneity and resource competition. An experiment with 4 cloud and edge sites over 300 cores shows how Storm-RTS can support flexible reconfiguration and simple high-level declarative policies that optimize resource cost or other criteria.

The growing use of computing and proliferation of computing devices requires a holistic focus on sustainability as the environmental impacts of computing technologies go beyond their energy consumption.Environmental impacts span all stages of the lifecycle -manufacturing, operation, and disposal.A sustainability mindset must permeate all organizations involved in design, manufacturing, operation, and disposal/recycling of computational devices.This panel will discuss current and new research on sustainability in computing that spans the full lifecycle, all layers of the computing stack and across the computing spectrum from edge to cloud.The panel will also discuss potential crossdisciplinary approaches to sustainable computing and new notions and metrics to quantify sustainability.

The growing use of computing and proliferation of computing devices requires a holistic focus on sustainability as the environmental impacts of computing technologies go beyond their energy consumption. Environmental impacts span all stages of the lifecycle - manufacturing, operation, and disposal. A sustainability mindset must permeate all organizations involved in design, manufacturing, operation, and disposal/recycling of computational devices. This panel will discuss current and new research on sustainability in computing that spans the full lifecycle, all layers of the computing stack and across the computing spectrum from edge to cloud. The panel will also discuss potential cross-disciplinary approaches to sustainable computing and new notions and metrics to quantify sustainability.

Data transformation tasks are a critical and costly part of many data processing and analytics applications. A simple computing model that can efficiently represent data transformation and be mapped to different platforms can provide programmers with the flexibility o f u sing different data representations and allow for exploiting different platforms, including general-purpose processors and accelerators.We propose extended Deterministic Finite State Transducers (DFST+s), a computing model that enables the compact expression of data transformations (a significantly terser expression compared to the DFSTs model, a traditional computational abstraction for data transformation), aiding their correct and efficient implementation. We define the TF ORM language to facilitate expressing the DFST+, and the TFORM virtual machine to enable a further compact expression, leading to a high performance and portable implementation. We propose two TFORM VM execution models and evaluate them using a variety of data transformations (from Apache Parquet file format and sparse matrices). Our results show both effective portability across CPU and a hardware accelerator, and performance increases of 1.7× and 11.7× geometric mean, respectively, over a custom CPU implementation of the same transformations.

Computational storage adds computing to storage devices, providing potential benefits in offload, data-reduction, and lower energy. Successful computational SSD architectures should match growing flash bandwidth, which in turn requires high SSD DRAM memory bandwidth. This creates a memory wall scaling problem, resulting from SSDs’ stringent power and cost constraints.A survey of recent computational SSD research shows that many computational storage offloads are suited to stream computing. To exploit this opportunity, we propose a novel general-purpose computational SSD and core architecture, called ASSASIN (Architecture Support for Stream computing to Accelerate computatIoNal Storage). ASSASIN provides a unified set of compute engines between SSD DRAM and the flash array. This eliminates the SSD DRAM bottleneck by enabling direct computing on flash data streams. ASSASIN further employs a crossbar to achieve performance even when flash data layout is uneven and preserve independence for page layout decisions in the flash translation layer. With stream buffers and scratchpad memories, ASSASIN core’s memory hierarchy and instruction set extensions provide superior low-latency access at low-power and effectively keep streaming flash data out of the in-SSD cache-DRAM memory hierarchy, thereby solving the memory wall.Evaluation shows that ASSASIN delivers 1.5x - 2.4x speedup for offloaded functions compared to state-of-the-art computational SSD architectures. Further, ASSASIN’s streaming approach yields 2.0x power efficiency and 3.2x area efficiency improvement. And these performance benefits at the level of computational SSDs translate to 1.1x - 1.5x end-to-end speedups on data analytics workloads.

Large Hadron Collider (LHC) produces collision data at 100 PB/year which needs to be stored and analyzed for high energy physics (HEP) theories. We reconsider the design choices of HEP data centers and evaluate different upgrade options to improve their analysis capacity.Results show that computational storage to be the cost-effective and power-efficient upgrade option. Computational disks in the storage cluster deliver a 9.3-fold speedup for Higgs Boson analysis. This exceeds the speedup from all other upgrades considered (faster network: 100 to 1000 Gbps, upgrade from HDDs to SSDs).

Shuffle is an indispensable process in distributed online analytical processing systems to enable task-level parallelism exploitation via multiple nodes. As a data-intensive data reorganization process, shuffle implemented on general-purpose CPUs not only incurs data traffic back and forth between the computing and storage resources, but also pollutes the cache hierarchy with almost zero data reuse. As a result, shuffle can easily become the bottleneck of distributed analysis pipelines.Our PSACS approach attacks these bottlenecks with the rising computational storage paradigm. Shuffle is offloaded to the storage-side PSACS accelerator to avoid polluting computing node memory hierarchy and enjoy the latency, bandwidth and energy benefits of near-data computing. Further, the microarchitecture of PSACS exploits data-, subtask-, and task-level parallelism for high performance and a customized scratchpad for fast on-chip random access.PSACS achieves 4.6x—5.7x shuffle throughput at kernel-level and up to 1.3x overall shuffle throughput with only a twentieth of CPU utilization comparing to software baselines. These mount up to 23% end-to-end OLAP query speedup on average.

Columnar databases rely on specialized encoding schemes to reduce storage requirements. These encodings also enable efficient in-situ data processing. Nevertheless, many existing columnar databases are encoding-oblivious. When storing the data, these systems rely on a global understanding of the dataset or the data types to derive simple rules for encoding selection. Such rule-based selection leads to unsatisfactory performance. Specifically, when performing queries, the systems always decode data into memory, ignoring the possibility of optimizing access to encoded data. We develop CodecDB, an encoding-aware columnar database, to demonstrate the benefit of tightly-coupling the database design with the data encoding schemes. CodecDB chooses in a principled manner the most efficient encoding for a given data column and relies on encoding-aware query operators to optimize access to encoded data. Storage-wise, CodecDB achieves on average 90% accuracy for selecting the best encoding and improves the compression ratio by up to 40% compared to the state-of-the-art encoding selection solution. Query-wise, CodecDB is on average one order of magnitude faster than the latest open-source and commercial columnar databases on the TPC-H benchmark, and on average 3x faster than a recent research project on the Star-Schema Benchmark (SSB).

Volatile resources are surplus cloud resources not consumed by high priority foreground (reserved/on-demand) load. These resources are exploited by a growing number of users. Today, cloud operators provide no statistical characterization of volatile resources. We consider how releasing such statistics could improve user value by studying Amazon's 608 EC2 Spot Instance types. Results show that as little as two parameters such as (average, 90pctile) can increase user value by 30%. These results are robust over four-fifths (475 of 608) of instance types. Beyond competitive concerns, cloud operators are reluctant to share volatile resource statistics because they might be considered a service-level agreement (SLA), and thus constrain their ability to serve foreground load. We show that clever resource management can allay such concerns. We study two plausible classes of foreground load changes, showing one class where such a concern is indeed valid and another where it is not. We design two online resource management algorithms that detect foreground load variation and adapt to maintain a statistical SLA. The algorithms not only improve the ability to maintain guarantees and user value but also improve user experience, reducing job failures by 50%. These results apply to the Stable and Transition classes of instance types, which account for nearly all of the instance types (577 of 608).

The data science revolution and growing popularity of data lakes make efficient processing of raw data increasingly important. To address this, we propose the ACCelerated Operators for Raw Data Analysis (ACCORDA) architecture. By extending the operator interface (subtype with encoding) and employing a uniform runtime worker model, ACCORDA integrates data transformation acceleration seamlessly, enabling a new class of encoding optimizations and robust high-performance raw data processing. Together, these key features preserve the software system architecture, empowering state-of-art heuristic optimizations to drive flexible data encoding for performance. ACCORDA derives performance from its software architecture, but depends critically on the acceleration of the Unstructured Data Processor (UDP) that is integrated into the memory-hierarchy, and accelerates data transformation tasks by 16x-21x (parsing, decompression) to as much as 160x (deserialization) compared to an x86 core. We evaluate ACCORDA using TPC-H queries on tabular data formats, exercising raw data properties such as parsing and data conversion. The ACCORDA system achieves 2.9x-13.2x speedups when compared to SparkSQL, reducing raw data processing overhead to a geomean of 1.2x (20%). In doing so, ACCORDA robustly matches or outperforms prior systems that depend on caching loaded data, while computing on raw, unloaded data. This performance benefit is robust across format complexity, query predicates, and selectivity (data statistics). ACCORDA's encoding-extended operator interface unlocks aggressive encoding-oriented optimizations that deliver 80% average performance increase over the 7 affected TPC-H queries.

Exascale systems face high error-rates due to increasing scale (109 cores), software complexity and rising memory error rates. Increasingly, errors escape immediate hardware-level detection, silently corrupting application states. Such latent errors can often be detected by application-level tests but typically at long latencies.

Power consumption and associated carbon emissions are increasingly critical challenges for large-scale computing. Recent research proposes exploiting stranded power - uneconomic renewable power - for green supercomputing in a system called Zero-Carbon Cloud (ZCCloud) [1], [2], [3]. These efforts studied production supercomputing workloads on stranded-power based computing resources, demonstrating their achievable productivity. We explore economic viability of stranded-power based supercomputing, using three datacenter total-cost-of-ownership (TCO) models to study cost-effectiveness. These studies show that ZCCloud's approach can be cost-effective in the USA today, and is even more attractive in regions with higher power prices (e.g., Japan, Germany), achieving cost advantages as large as 50 percent. Environmental and power-grid benefits are a further advantage. We also explore the sensitivity of these results to changes in hardware TCO; cheaper hardware or longer lifetimes magnify the attractiveness of stranded-power based approaches, yielding advantages as large as 91 percent. These results are robust across different TCO models. Finally, we study extreme-scale supercomputers (>100 MW), finding stranded-power can increase peak capability per cost by as much as 80 percent.

Traditional cloud stacks are designed to tolerate random, small-scale failures, and can successfully deliver highly-available cloud services and interactive services to end users. However, they fail to survive large-scale disruptions that are caused by major power outage, cyber-attack, or region/zone failures. Such changes trigger cascading failures and significant service outages. We propose to understand the reasons for these failures, and create reliable data services that can efficiently and robustly tolerate such large-scale resource changes.

Projections and measurements of error rates in near-exascale and exascale systems suggest a dramatic growth, due to extreme scale (10^9 cores), concurrency, software complexity, and deep submicron transistor scaling. Such a growth makes resilience a critical concern, and may increase the incidence of errors that "escape", silently corrupting application state. Such errors can often be revealed by application software tests but with long latencies, and thus are known as latent errors. We explore how to efficiently recover from latent errors, with an approach called application-based focused recovery (ABFR). Specifically we present a case study of stencil computations, a widely useful computational structure, showing how ABFR focuses recovery effort where needed, using intelligent testing and pruning to reduce recovery effort, and enables recovery effort to be overlapped with application computation. We analyze and characterize the ABFR approach on stencils, creating a performance model parameterized by error rate and detection interval (latency). We compare projections from the model to experimental results with the Chombo stencil application, validating the model and showing that ABFR on stencil can achieve a significant reductions in error recovery cost (up to 400x) and recovery latency (up to 4x). Such reductions enable efficient execution at scale with high latent error rates.

Big data analytic applications give rise to large-scale extract-transform-load (ETL) as a fundamental step to transform new data into a native representation. ETL workloads pose significant performance challenges on conventional architectures, so we propose the design of the unstructured data processor (UDP), a software programmable accelerator that includes multi-way dispatch, variable-size symbol support, Flexible-source dispatch (stream buffer and scalar registers), and memory addressing to accelerate ETL kernels both for current and novel future encoding and compression. Specifically, UDP excels at branch-intensive and symbol and pattern-oriented workloads, and can offload them from CPUs.

MittOS provides operating system support to cut millisecond-level tail latencies for data-parallel applications. In MittOS, we advocate a new principle that operating system should quickly reject IOs that cannot be promptly served. To achieve this, MittOS exposes a fast rejecting SLO-aware interface wherein applications can provide their SLOs (e.g., IO deadlines). If MittOS predicts that the IO SLOs cannot be met, MittOS will promptly return EBUSY signal, allowing the application to failover (retry) to another less-busy node without waiting. We build MittOS within the storage stack (disk, SSD, and OS cache managements), but the principle is extensible to CPU and runtime memory managements as well. MittOS' no-wait approach helps reduce IO completion time up to 35% compared to wait-then-speculate approaches.

Flash storage has become the mainstream destination for storage users. However, SSDs do not always deliver the performance that users expect. The core culprit of flash performance instability is the well-known garbage collection (GC) process, which causes long delays as the SSD cannot serve (blocks) incoming I/Os, which then induces the long tail latency problem. We present tt F lash as a solution to this problem. tt F lash is a “tiny-tail” flash drive (SSD) that eliminates GC-induced tail latencies by circumventing GC-blocked I/Os with four novel strategies: plane-blocking GC, rotating GC, GC-tolerant read, and GC-tolerant flush. These four strategies leverage the timely combination of modern SSD internal technologies such as powerful controllers, parity-based redundancies, and capacitor-backed RAM. Our strategies are dependent on the use of intra-plane copyback operations. Through an extensive evaluation, we show that tt F lash comes significantly close to a “no-GC” scenario. Specifically, between the 99 and 99.99th percentiles, tt F lash is only 1.0 to 2.6× slower than the no-GC case, while a base approach suffers from 5–138× GC-induced slowdowns.

In supercomputer centers, available power, cooling, or carbon footprint often limits supercomputer performance. We propose a new approach to continue scaling that avoids many of these limits, augmenting a traditional system with another that employs only "wasted" renewable power, stranded power. This excess power cannot be economically distributed through grid, and is only intermittently available. We call this approach Zero-carbon Cloud (ZCCloud). We explore the potential benefits of unreliable resources with production DOE HPC workloads using a simple periodic model, and identify job types that benefit most (capability jobs and on-time jobs). The benefits scale with duty factor and resource quantity. Next, to create realistic models of "stranded power" we study 28 months of Mid-continent Independent System Operator (MISO) power market history (1,259 generators, 77 million 5-minute intervals). We find that opportunity varies, but the best single wind site can provide 80% duty factor, and 20MW average stranded power. Combining sites further improves duty factor. With resource volatility models from the MISO study, we simulate production DOE HPC workloads and find that stranded power HPC, ZCCloud, can provide significant benefit, decreasing average job-wait time by 50%.

Classical models for distributed systems focus on fine-grained resources and failures (e.g. single processes and fail-stop or byzantine). Cheap hardware, the rise of the worldwide web, and now the rise of cloud computing has transformed distributed systems practice. Instead of single resources, application sites have ten-thousands of virtual machines, and in addition to independent failures, there are a raft of correlated failure modes.

Supercomputing platforms are expected to have larger failure rates in the future because of scaling and power concerns. The memory and performance impact may vary with error types and failure modes. Therefore, localized recovery schemes will be important for scientific computations, including failure modes where application intervention is suitable for recovery. We present a resiliency methodology for applications using structured adaptive mesh refinement, where failure modes map to granularities within the application for detection and correction. This approach also enables parameterization of cost for differentiated recovery. The cost model is built with tuning parameters that can be used to customize the strategy for different failure rates in different computing environments. We also show that this approach can make recovery cost proportional to the failure rate.

In this paper, we perform a systematic comparison to study the energy cost of varying data formats and data types w.r.t. arithmetic logic and data movement for accelerator-based heterogeneous systems in which both compute-intensive (FFT accelerator) and data-intensive accelerators (DLT accelerator) are added. We explore evaluation for a wide range of design processes (e.g. 32nm bulk-CMOS and projected 7nm FinFET) and memory systems (e.g. DDR3 and HMC). First, our result shows that when varying data formats, the energy costs of using floating point over fixed point are 5.3% (DDR3), 6.2% (HMC) for core and 0.8% (DDR3), 1.5% (HMC) for system in 32nm process. These energy costs are negligible as 0.2% and 0.01% for core and system in 7nm FinFET process in DDR3 memory and slightly increasing in HMC. Second, we identify that the core and system energy of systems using fixed point, 16-bit, FFT accelerator is nearly half of using 32-bit if data movement is also accelerated. This evidence implies that system energy is highly proportional to the amount of moving data when varying data types.

In exascale systems, increasing error rate -- particularly silent data corruption -- is a major concern. The Global ViewResilience (GVR) system builds a new model of application resilience on versioned global arrays. These arrays can be exploited for flexible, application-specific error checking and recovery. We explore a fundamental challenge to the GVR model -- the cost of versioning. We propose a novel log-structured implementation that appends new data to an update log, simultaneously tracking modified regions and versioning incrementally. We compare performance of log-structured arrays to traditional flat arrays using micro-benchmarks and three full applications, and show that versioning can be more than 10x faster, and reduce memory cost significantly. Further, in future systems with NVRAM, a log-structured approach is more tolerant onramp limitations such as write bandwidth and wear-out.

We present the Global View Resilience (GVR) system, a library that enables applications to add resilience in a portable, application-controlled fashion using versioned distributed arrays. We briefly describe GVR's interfaces for distributed arrays, versioning, and cross-layer error recovery. We illustrate how GVR can be used for rollback recovery and a wide range additional error recovery techniques including forward recovery for latent errors or silent data corruptions. Application results demonstrate that GVR's interfaces and implementation are portable, flexible (support a variety of recovery models), efficient and create a gentle-slope path to tolerate growing error rates in future systems.

Future supercomputer systems will face serious reliability challenges. Among failure scenarios, latent errors are some of the most serious and concerning. Preserving multiple versions of critical data is a promising approach to deal with such errors. We are developing the Global View Resilience (GVR) library, with multi-version global arrays as one of the key features. This paper presents three array versioning architectures: flat array, flat array with change tracking, and log-structured array. We use a synthetic workload comparing the three array architectures in terms of runtime performance and memory requirements. The experiments show that the flat array with change tracking is the best architecture in terms of runtime performance, for versioning frequencies of 10-5ops-1or higher matching the second best architecture or beating it by over 8 times, whereas the log-structured array is preferable for low memory usage, since it saves up to 88% of memory compared with a flat array.

Energy is a critical challenge in computing performance. Due to "word size creep" from modern CPUs are inefficient for short-data element processing. We propose and evaluate a new microarchitecture called "Bit-Nibble-Byte"(BnB). We describe our design which includes both long fixed point vectors and as well as novel variable length instructions. Together, these features provide energy and performance benefits on a wide range of applications. We evaluate BnB with a detailed design of 5 vector sizes (128,256,512,1024,2048) mapped into 32nm and 7nm transistor technologies, and in combination with a variety of memory systems (DDR3 and HMC). The evaluation is based on both handwritten and compiled code with a custom compiler built for BnB. Our results include significant performance (19x-252x) and energy benefits (5.6x-140.7x) for short bit-field operations typically assumed to require hardwired accelerators and large-scale applications with compiled code.

Graph processing is important for a growing range of applications. Current performance studies of parallel graph computation employ a large variety of algorithms and graphs. To explore their robustness, we characterize behavior variation across algorithms and graph structures at different scales. Our results show that graph computation behaviors, with up to 1000-fold variation, form a very broad space. Any inefficient exploration of this space may lead to narrow understanding and ad-hoc studies. Hence, we consider constructing an ensemble of graph computations, or graph-algorithm pairs, to most effectively explore this graph computation behavior space. We study different ensembles of parallel graph computations, and define two metrics to quantify how efficiently and completely an ensemble explores the space. Our results show that: (1) experiments limited to a single algorithm or a single graph may unfairly characterize a graph-processing system, (2) benchmarks exploring both algorithm and graph diversity can significantly improve the quality (30% more complete and 200% more efficient), but must be carefully chosen, (3) some algorithms are more useful than others in benchmarking, and (4) we can reduce the complexity (number of algorithms, graphs, runtime) while conserving the benchmarking quality.

Future supercomputer systems will face serious reliability challenges. Among failure scenarios, latent errors are some of the most serious and concerning. Preserving multiple versions of critical data is a promising approach to deal with such errors. We are developing the Global View Resilience (GVR) library, with multi-version global arrays as one of the key features. This paper presents three array versioning architectures: flat array, flat array with change tracking, and log-structured array. We use a synthetic workload that mimics the memory access patterns of radix sort, N-body simulation, and matrix multiplication, comparing the three array architectures in terms of runtime performance, memory requirements, and version restoration costs. The experiments show that the flat array with change tracking is the best architecture in terms of runtime performance, for versioning frequencies of 10-5ops-1or higher matching the second best architecture or beating it by up to 23 times, whereas the log-structured array is preferable for low memory usage, since it saves up to 98% of memory compared with a flat array.

We propose the Unified Automata Processor (UAP), a new architecture that provides general and efficient support for finite automata (FA). The UAP supports a wide range of existing finite automata models (DFAs, NFAs, A-DFAs, JFAs, counting-DFAs, and counting-NFAs), and future novel FA models. Evaluation on realistic workloads shows that UAP implements all models efficiently, achieving line rates 94.5% of ideal. A single UAP lane delivers line rates 50x greater than software approaches on CPUs and GPUs. Scaling UAP to 64 lanes achieves FA transition throughputs as high as 295 Gbps, more than 100x higher than CPUs and GPUs, and even exceeding ASIC approaches such as IBM's RegX by 6x. With efficient support for multiple input streams, UAP achieves throughputs that saturate even high speed stacked DRAM memory systems.

Emerging exascale architectures bring forth new challenges related to heterogeneous systems power, energy, cost, and resilience. These new challenges require a shift from conventional paradigms in understanding how to best exploit and optimize these features and limitations. Our objective is to identify the top few dominant characteristics in a set of applications. Understanding these characteristics will allow the community to build and exploit customized architectures and tools best suited to optimize each dominant characteristic in the application domain. Every application will typically be composed of multiple characteristics and thus will use several of the customized accelerators and tools during its execution phases, with the eventual goal of using the entire system efficiently. In this poster, we describe a hybrid methodology, based on binary instrumentation, for characterizing scientific applications such as instruction mix and memory access patterns. We apply our methodology to proxy applications that are representative of a broad range of DOE scientific applications. With this empirical basis, we develop and validate statistical models that extrapolate application properties as a function of problem size. These models are then used to project the first quantitative characterization of an exascale computing workload, including computing and memory requirements. We evaluate the potential benefit of processor under memory, a radical new exascale architecture customization and understand how these new customization can impact applications.

The collision of large-scale computational capabilities (multi-core) and system-scale integration (system-on-chip) have produced a landscape in which networks-on-chip are a central critical element of system design. However, the traditional approaches and requirements from these two communities are quite different with divergence in requirements of cost, regularity, power, methodology, compatibility, features, etc. This talk will survey the landscape of modern NoC design, and point out challenging new opportunities and directions for the NoC research community. Open challenges include-how to reconcile performance with cost, what functions are within scope for NoC, how to reconcile performance with heterogeneity, how to reconcile performance with long-term compatibility, and so on. The central architectural importance of networks-on-chip are now clear, the challenges are to define the architectural approaches and paths which enable robust, efficient, high-performance, cost-effective, and of course rapidly designed systems.

No abstract available.

No abstract available.

We present and analyze techniques to efficiently solve the partial content distribution problem – distributing a logical data set to receivers which individually desire only subsets of the total data. This is a more general and fundamentally different problem than traditional whole-file content distribution; providing new challenges and new optimization opportunities. It supports a wider variety of use models, e.g., striped file transfer, scatter/gather, or distributed editing. This work develops new metadata management and transfer scheduling techniques providing good results on high performance networks. Distributed applications in such systems tend to have data requirements more complicated than just total overlap at every node: transfers desired differ dramatically from whole-file content distribution. Traditional approaches perform poorly in such cases. We provide empirical data exhibiting these limitations, evaluate a new BitTorrent-based implementation of our ideas, and show order of magnitude improvements in bandwidth and latency.

Parallel programming has been the subject of deep research for decades -- and renowned in the software community as a difficult challenge to the degree that many companies have teams of parallelism and concurrency experts. Further, many ISV's explicitly design their software architectures so as to ensure that the majority of the development effort, including of course debug and test, can be done without consideration of parallelism. What makes parallelism so difficult, are the knotty and coupled problems of correctness, performance -- particularly data locality, and software modularity.

With an increasing number of available resources in large-scale distributed environments, a key challenge is resource selection. Fortunately, several middleware systems provide resource selection services. However, a user is still faced with a difficult question: "What should I ask for?" Since most users end up using naïve and suboptimal resource specifications, we propose an automated way to answer this question. We present an empirical model that given a workflow application (DAG-structured) generates an appropriate resource specification, including number of resources, the range of clock rates among the resources, and network connectivity. The model employs application structure information as well as an optional utility function that trades off cost and performance. With extensive simulation experiments for different types of applications, resource conditions, and scheduling heuristics, we show that our model leads consistently to close to optimal application performance and often reduces resource usage.

A critical challenge for wide-area configurable networks is definition and widespread acceptance of Network Information Model (NIM). When a network comprises multiple domains, intelligent information sharing is required for a provider to maintain a competitive advantage and for customers to use a provider's network and make good resource selection decisions. We characterize the information that can be shared between domains and propose a spectrum of network information models. To evaluate the impact of the proposed models, we use a trace-driven simulation under a range of real providers' networks and assess how the available information affects applications' and providers' ability to utilize network resources. We find that domain topology information is crucial for achieving good resource efficiency, low application latency and network configuration cost, while domain link state information contributes to better resource utilization and system throughput. These results suggest that collaboration between service providers can provide better overall network productivity.

Emerging large-scale scientific applications require to access large data objects in high and robust performance. We propose RobuSTore, a storage architecture that combines erasure codes and speculative access mechanisms for parallel write and read in distributed environments. The mechanisms can effectively aggregate the bandwidth from a large number of distributed disks and statistically tolerate pear-disk performance variation. Our simulation results affirm the high and robust performance of RobuSTore in both write and read operations compared to traditional parallel storage systems. For example, for a 1GB data access using 64 disks, RobuSTore achieves average bandwidth of 186MBps for write and 400MBps for read, nearly 6x and 15x that achieved by a RAID-0 system. The standard deviation of access latency is only 0.5 second, about 9% of the write latency and 20% of the read latency, and a 5-fold improvement from RAID-0. The improvements are achieved at moderate cost: about 40% increase in I/O operations and 2x-3x increase in storage capacity utilization.

Over the past years grid infrastructures have been deployed at larger and larger scales, with envisioned deployments incorporating tens of thousands of resources. Therefore, application scheduling algorithms can become unscalable (albeit polynomial) and thus unusable in large-scale environments. One reason for unscalability is that these algorithms perform implicit resource selection. One can achieve better scalability by performing explicit resource selection independently from scheduling in a "decoupled' approach. Furthermore, we hypothesize that one can achieve similar or even better performance as with the non-decoupled approach, which we call the "one step" approach, by selecting resources judiciously. Leveraging the Virtual Grid abstraction, we demonstrate that the decoupled approach is indeed both scalable and effective in large-scale and highly heterogeneous resource environments.

Desktop grids, which use the idle cycles of many desktop PC's, are currently one of the largest distributed systems in the world. Despite the popularity and success of many desk-top grid projects, the volatility of hosts within desktop grids has been poorly understood. Yet, such host characterization is essential for accurate simulation and modelling of such platforms. In this paper, we present application-level traces of four enterprise desktop grids with a wide range of user bases. We then describe aggregate and per host statistics that reflect the volatility of desktop grid resources. Further, we determine the correlation of volatility between resources, and investigate the correlation of volatility and other host characteristics. Finally, we detail a number of implications of these findings with respect to application performance.

This paper presents a new formulation of the resource selection and binding problem and proposes a new algorithm called integrated selection and binding to solve this problem. Our insight is that a resource selection algorithm should consider binding failures. Consequently, the key idea of the integrated selection and binding approach is to decompose a resource collection request into components that can be bound and composed independently and to select multiple sets of resources for each component. The integrated approach is more efficient and effective than the separate approach for competitive access to federated resources

Users and developers of grid applications have access to increasing numbers of resources. While more resources generally mean higher capabilities for an application, they also raise the issue of application scheduling scalability. First, even polynomial time scheduling heuristics may take a prohibitively long time to compute a schedule. Second, and perhaps more critical, it may not be possible to gather all the resource information needed by a scheduling algorithm in a scalable manner. Our application focus is scientific workflows, which can be represented as directed acyclic graphs (DAGs). Our claim is that, in future resource-rich environments, simple scheduling algorithms may be sufficient to achieve good workflow performances. We introduce a scalable scheduling approach that uses a resource abstraction called a virtual grid (VG). Our simulations of a range of typical DAG structures and resources demonstrate that a simple greedy scheduling heuristic combined with the virtual grid abstraction is as effective and more scalable than more complex heuristic DAG scheduling algorithms on large-scale platforms

Media companies (and other organizations with large amounts of digital content) require prompt broadcast of extremely large files from a single source to a collection of geographically dispersed destinations. Due to the high cost of terrestrial networks of sufficient bandwidth, satellite networks are commonly used for such transfers. However, current satellite transfers rely on expensive error correction via forward error correction and whole-file retransmission. This paper presents a new, hybrid solution combining the advantages of satellite and terrestrial networks to provide cost-effective reliable file transfer. Specifically, we propose a new peer-to-peer scheme exploiting fast terrestrial networks and multiple receivers to recover from high loss rates (5% or more) in near real-time (latency < 400ms). This solution is efficient, robust under variable packet loss and connectivity, user tunable, scales well, and doubles bandwidth compared to existing approaches. The system has been validated via extensive simulations using a terrestrial network based on the AT&T common backbone core network

Discovering and acquiring appropriate, complex resource collections in large-scale distributed computing environments is a fundamental challenge and is critical to application performance. This paper presents a new formulation of the resource selection problem and a new solution to the resource selection and binding problem called integrated selection and binding. Composition operators in our resource description language and efficient data organization enable our approach to allocate complex resource collections efficiently and effectively even in the presence of competition for resources. Our empirical evaluation shows that the integrated approach can produce solutions of significantly higher quality at higher success rate and lower cost than the traditional separate approach. The success rate of the integrated approach can tolerate as much as 15%-60% lower resource availability than the separate approach. Moreover, most requests have at least the 98th percentile rank and can be served in 6 seconds with a population of 1 million hosts.

Simple resource specification, resource selection, and effective binding are critical capabilities for grid middleware. We describe the virtual grid, an abstraction for providing these capabilities complex resource environments. Elements of the virtual grid include a novel resource description language (vgDL) and a resource selection and binding component (vgFAB), which accepts a vgDL specification and returns a virtual grid, that is, a set of selected and bound resources. The goals of vgFAB are efficiency, scalability, robustness to high resource contention, and the ability to produce results with quantifiable high quality. We present the design of vgDL, showing how it captures application-level resource abstractions using resource aggregates and connectivity amongst them. We present and evaluate a prototype implementation of vgFAB. Our results show that resource selection and binding for virtual grids of 10,000's of resources can scale up to grids with millions of resources, identifying good matches in less than one second. Further, these matches have quantifiable quality, enabling applications to have high confidence in the results. We demonstrate the effectiveness of our combined selection and binding approach in the presence of resource contention, showing that robust selection and binding can be achieved at moderate cost.

We introduce the Composite Endpoint Protocol (CEP), which efficiently composes a set of transmission elements to support high speed flows which exceed the capabilities of a single computer. CEP's unique capabilities include: (1) allowing multiple processes (a composite endpoint) to take part in a single logical connection, (2) providing a simple, flexible interface to describe data layouts and composite endpoint communication to user programs, (3) providing efficient transfer scheduling which coordinates heterogeneous nodes to achieve good composite performance, and (4) a scalable architecture which supports large numbers of participants in a composite endpoint. We describe the design of CEP, an initial implementation, and an empirical evaluation exhibiting the above capabilities. We have achieved speeds over 32 Gbps using commodity cluster hardware with linear scalability performance 7x naive approaches, and low overhead.

Grid computing infrastructures and applications are increasingly diverse with networks ranging from very high bandwidth optical networks to wireless networks and applications ranging from remote visualization to sensor data collection. For such environments, standard transport protocols such as TCP and UDP are not always sufficient or optimal given their fixed set of properties and their lack of flexibility. As an alternative, we present H-CTP, a high-performance configurable transport protocol that can be used to build customized transport services for a wide range of grid computing scenarios. H-CTP is based on an earlier configurable transport protocol called CTP, but with a collection of optimizations that meet the challenge of providing configurability while maintaining performance that meets the requirements of such demanding applications. This paper motivates the need for customizable transport in this area, presents the design of H-CTP, and gives results from performance studies that compare H-CTP with both CTP and TCP. These show, for example, that H-CTP is able to achieve throughput of over 900 Mbps across Gigabit links. Three diverse grid scenarios are used as example applications and for the H-CTP/TCP comparisons: remote visualization, fast message passing, and sensor grids.

Power consumption has become one of the first order design considerations of the nano-scale VLSI designs. In this paper, we propose a methodology to synthesize energy-efficient networks-on-chip (NoCs). Our methodology features three key characters. First, we adopt a multi-commodity flow formulation to unify network topologies, physical embedding, and wire style optimizations. Second, we utilize a variety of interconnect wire styles to achieve high performance low power on-chip communication. Third, we heuristically explore a large design space of network topologies. Experiments on a homogeneous communication demand model demonstrate that for a 4 /spl times/ 4 NoC with torus topology, our methodology can achieve a power saving up to 35%.

No abstract available.

Desktop distributed computing allows companies to exploit the idle cycles on pervasive desktop PC systems to increase the available computing power by orders of magnitude (10x - 1000x). Applications are submitted, distributed, and run on a grid of desktop PCs. Since the applications may be malformed, or malicious, the key challenges for a desktop grid are how to 1) prevent the distributed computing application from unwarranted access or modification of data and files on the desktop PC, 2) control the distributed computing application's resource usage and behavior as it runs on the desktop PC, and 3) provide protection for the distributed application's program and its data. In this paper we describe the Entropia Virtual Machine, and the solutions it embodies for each of these challenges.

Abstract Few methods use molecular dynamics simulations in concert with atomically detailed force fields to perform protein–ligand docking calculations because they are considered too time demanding, despite their accuracy. In this paper we present a docking algorithm based on molecular dynamics which has a highly flexible computational granularity. We compare the accuracy and the time required with well‐known, commonly used docking methods such as AutoDock, DOCK, FlexX, ICM, and GOLD. We show that our algorithm is accurate, fast and, because of its flexibility, applicable even to loosely coupled distributed systems such as desktop Grids for docking. Copyright © 2005 John Wiley & Sons, Ltd.

Many applications in cluster computing require QoS (quality of service) services. Since performance predictability is essential to provide QoS service, underlying systems must provide predictable performance guarantees. One way to ensure such guarantees from network subsystems is to generate global schedules from applications' network requests and to execute the local portion of the schedules at each network interface. To ensure accurate execution of the schedules, it is essential that a global time base must be maintained by local clocks at each network interface. The task of providing a single time base is called a synchronization problem and this paper addresses the problem for system area networks. To solve the synchronization problem, FM-QoS [K. Connelly (1999)] proposed a simple synchronization mechanism called FBS (feedback-based synchronization) which uses built-in flow control signals. This paper extends the basic notion of FM-QoS to a theoretical framework and generalizes it: 1) to identify a set of built-in network flow control signals for synchrony and to formalize it as a synchronizing schedule and 2) to analyze the synchronization precision of FBS in terms of flow control parameters. Based on generalization, two application classes are studied for a single switch network and a multiple switch network. For each class, a synchronizing schedule is proposed and its bounded skew is analyzed. Unlike FM-QoS, the synchronizing schedule is proven to minimize the bounded skew value for a single switch network. To understand the analysis results in practical networks, skew values are obtained with flow control parameters of Myrinet-2000. We observed that the maximum bounded skew of FBS is 5.79/spl mu/sec or less over all our experiments. Based on this result, we came to a conclusion that FBS was a feasible synchronization mechanism in system area networks.

The distributed virtual computer (DVC) is a computing environment, which simplifies the development and execution of distributed applications on computational Grids. DVC provides a simple set of abstractions to simplify application management of naming, security, communication, and resource, easing use of highly dynamic and heterogeneous resource environments. These abstractions enable complex collections of Grid resources to be used in a fashion similar to private user or workgroup resources. The DVC model is attractive for lambda-Grids with circuit-switched optical networks, providing a structure for exploiting unique communication and security properties. Examples of DVC include virtual clusters and virtual heterogeneous resource collections. We introduce the concept of a DVC, its system structure and mechanisms. We discuss the potential benefits of DVC for application programmers.

The notion of lambda-Grids posits plentiful collections of computing and storage resources richly interconnected by dedicated dense wavelength division multiplexing (DWDM) optical paths. In lambda-Grids, the DWDM links form a network with plentiful bandwidth, pushing contention and sharing bottlenecks to the end systems (or their network links) and motivating the group transport protocol (GTP). GTP features a request-response data transfer model, rate-based explicit flow control, and more importantly, receiver-centric max-min fair rate allocation across multiple flows to support multipoint-to-point data movement. Our studies show that GTP performs as well as other UDP based aggressive transport protocols (e.g. RBUDP, SABUL) for single flows, and when converging flows (from multiple senders to one receiver) are introduced, GTP achieves both high throughput and much lower loss rates than others. This superior performance is due to new techniques in GTP for managing end system contention.

We are developing application abstractions called distributed virtual computers (DVC), which simplify application use of dynamic optical resources. DVC descriptions naturally express communication and computation resource requirements, enabling coordinated resource binding. We describe initial experience with DVCs and how they provide an integrating architecture for lambda grids. The OptIPuter project is a large multiinstitutional project led by Larry Smarr at the University of California, San Diego (UCSD) and Tom DeFanti at the University of Illinois at Chicago (UIC). Other software efforts include optical signaling software, visualization, distributed configuration management, and two driving applications involving petabytes of data. We are also constructing a high-speed OptIPuter testbed.

Summary form only given. Accurate, continuous resource monitoring and profiling are critical for enabling performance tuning and scheduling optimization. In desktop grid systems that employ sandboxing, these issues are challenging because (1) subjobs inside sandboxes are executed in a virtual computing environment and (2) the state of the virtual computing environment within the sandboxes is reset to empty after each subjob completes. DGMonitor is a monitoring tool, which builds a global, accurate, and continuous view of real resource utilization for desktop grids with sandboxing. Our monitoring tool measures performance unobtrusively and reliably, uses a simple performance data model, and is easy to use. Our measurements demonstrate that DGMonitor can scale to large desktop grids (up to 12000 workers) with low monitoring overhead in terms of resource consumption (less than 0.1%) on desktop PCs. Though we developed DGMonitor with the Entropia DCGrid platform, our tool is easily integrated into other desktop grid systems. In all of these systems, DGMonitor data can support existing and novel information services, particularly for performance tuning and scheduling.

Summary form only given. Desktop resources are attractive for running compute-intensive distributed applications. Several systems that aggregate these resources in desktop grids have been developed. While these systems have been successfully used for many high throughput applications there has been little insight into the detailed temporal structure of CPU availability of desktop grid resources. Yet, this structure is critical to characterize the utility of desktop grid platforms for both task parallel and even data parallel applications. We address the following questions: (i) What are the temporal characteristics of desktop CPU availability in an enterprise setting? (ii) How do these characteristics affect the utility of desktop grids? (iii) Based on these characteristics, can we construct a model of server "equivalents" for the desktop grids, which can be used to predict application performance? We present measurements of an enterprise desktop grid with over 220 hosts running the Entropia commercial desktop grid software. We utilize these measurements to characterize CPU availability and develop a performance model for desktop grid applications for various task granularities, showing that there is an optimal task size. We then use a cluster equivalence metric to quantify the utility of the desktop grid relative to that of a dedicated cluster.

Summary form only given. Few methods use molecular dynamics simulations based on atomically detailed force fields to study the protein-ligand docking process because they are considered too time demanding despite their accuracy. We present a docking algorithm based on molecular dynamics simulations which has a highly flexible computational granularity. We compare the accuracy and the time required with well-known, commonly used docking methods like AutoDock, DOCK, FlexX, ICM, and GOLD. We show that our algorithm is accurate, fast and, because of its flexibility, applicable even to loosely coupled distributed systems like desktop grids for docking.

Understanding large Grid platform configurations and generating representative synthetic configurations is critical for Grid computing research. This paper presents an analysis of existing resource configurations and proposes a Grid platform generator that synthesizes realistic configurations of both computing and communication resources. Our key contributions include the development of statistical models for currently deployed resources and using these estimates for modeling the characteristics of future systems. Through the analysis of the configurations of 114 clusters and over 10,000 processors, we identify appropriate distributions for resource configuration parameters in many typical clusters. Using well-established statistical tests, we validate our models against a second resource collection of 191 clusters and over 10,000 processors, and show that our models effectively capture the resource characteristics found in real world resource infrastructures. These models are realized in a resource generator, which can be easily recalibrated by running it on a training sample set.

Desktop grids are popular platforms for high throughput applications, but due their inherent resource volatility it is difficult to exploit them for applications that require rapid turnaround. Efficient desktop grid execution of short-lived applications is an attractive proposition and we claim that it is achievable via intelligent resource selection. We propose three general techniques for resource selection: resource prioritization, resource exclusion, and task duplication. We use these techniques to instantiate several scheduling heuristics. We evaluate these heuristics through trace-driven simulations of four representative desktop grid configurations. We find that ranking desk-top resources according to their clock rates, without taking into account their availability history, is surprisingly effective in practice. Our main result is that a heuristic that uses the appropriate combination of resource prioritization, resource exclusion, and task replication achieves performance within a factor of 1.7 of optimal.

Large-scale network simulation is an important technique for studying the dynamic behavior of networks, network protocols, and emerging classes of distributed application (e.g. Grid, peer-to-peer, etc.) Large-scale and realism are two critical requirements for network simulations of Grid application studies. Our work here extends previous efforts in three key ways. First, we study networks 100x larger than in our previous studies (20,000 routers). Second, at this scale, we study realistic network struct ures (100 AS’s, BGP4 and OSPF routing) versus flat OSPF routing. Finally, we describe and evaluate a new profile-based load-balancing approach called hierarchical profile-based load balance. Our extensive large-scale experiments with profile-based load balance (PROF) on flat-routed (OSPF) networks show that PROF outperforms several other techniques based on topology and static application information. However, these results and those for multi-AS networks motivate our invention of a new hierarchical technique (HPROF) which clusters network nodes to achieve a desired minimum link latency (MLL), a key determinant of simulation parallelism, then applies the graph partitioner. HPROF explicitly controls the tradeoff between simulation efficiency and available parallelism, producing robust and superior performance for large-scale networks, including both single-AS and multi-AS networks. HPROF can improve load imbalance by 40%, and reduce the simulation time by about 50% in our 20,000 router simulations executed on 128-node clusters. The parallel efficiency achieved by these simulations is over 40%, providing substantial capabilities for simulating large networks. In summary, these advances demonstrate that realistic large-scale network simulation for networks of 20,000 routers (comparable to a large Tier-1 ISP network like AT&T) can be accomplished with our system.

Load balance is critical to achieving scalability for large network emulation studies, which are of compelling interest for emerging Grid, Peer to Peer, and other distributed applications and middleware. Achieving load balance in emulation is difficult because of irregular network structure and unpredictable network traffic. We formulate load balance as a graph partitioning problem and apply classical graph partitioning algorithms to it. The primary challenge in this approach is how to extract useful information from the network emulation and present it to the graph partitioning algorithms in a way that reflects the load balance requirement in the original emulation problem. Using a large-scale network emulation system called MaSSF, we explore three approaches for partitioning, based on purely static topology information (TOP), combining topology and application placement information (PLACE), and combining topology and application profile data (PROFILE). These studies show that exploiting static topology and application placement information can achieve reasonable load balance, but a profile-based approach further improves load balance for even large scale network emulation. In our experiments, PROFILE improves load balance by 50% to 66% and emulation time is reduced up to 50% compared to purely static topology-based approaches.

Distributed Computing, the exploitation of idle cycles on pervasive desktop PC systems, offers the opportunity to increase the available computing power by orders of magnitude (10× to 1000×). Such large-scale resource sharing is a key part of the emerging “Grid” computing technologies being developed and pursued by a broad array of researchers, software vendors, and hardware vendors. However, for desktop PC distributed computing to be widely accepted within the enterprise, the systems must achieve high levels of robustness, security, scalability, unobtrusiveness, and manageability. In addition, as with any novel platform technology, the systems must also capture a critical mass of applications that make the platform valuable. We describe the emerging distributed computing technologies, focusing in particular on their system architecture and approaches to solve the key challenges. We will describe the Entropia system as a case study, detailing its internal architecture and philosophy in attacking these key problems. In particular, key aspects of the Entropia system include the use of • scalable web/database technology for system management • network tunneling and application namespaces for logical connectivity • binary sandboxing technology for security and unobtrusiveness • open integration model to allow applications from many sources to be incorporated We describe the Entropia system and how these technologies are combined to produce a robust, flexible, high-performance system which is in use in numerous enterprises supporting a wide range of applications. One promising area for distributed computing is a cluster of applications that support early drug discovery. Computational demands in this area are growing in accord with Venter’s Law, a more rapid increase than Moore’s Law. We discuss applications from Bioinformatics or Computational Chemistry, which all involve large numbers of parallel runs without dependencies between them (“embarrassingly parallel” jobs). In addition, most of the applications involve the use of significant quantities of data (either sequence or molecular databases), and large amounts of computation. We will describe several of these applications and give examples of how they are used in early drug discovery—a critical factor that determines their scale-up needs. We also describe their performance in a distributed computing system.

An essential building block for any data grid infrastructure is the storage server. In this paper we describe a high-performance cluster storage server built around the SDSC Storage Resource Broker (SRB) and commodity workstations. A number of performance critical design issues and our solutions to them are described. We incorporate pipeline optimizations into SRB to enable the full overlapping of communication and disk I/O. With these optimizations we were able to deliver to the application more than 95% of the disk throughput achievable through a remote connection. Then we show how our approach to network-striped transport is effective in achieving aggregate cluster-to-cluster throughput which scales with the number of connections. Finally, we present a federated SRB service over MPI that allows fast TCP connections to stripe data across multiple server disks reaching 97% of the combined write capacity of multiple nodes.

This paper attempts to reconcile the high performance community's requirement of high performance with the need for security, and reconcile some accepted security approaches with the performance constraints of high-performance networks. We propose a new paradigm and challenge existing practice. The new paradigm is that not all domains need longterm forward data confidentiality. In particular, we take a fresh look at security for the high-performance domain, focusing particularly on component-based applications. We discuss the security and performance requirements of this domain in order to elucidate both the constraints and opportunities. We challenge the existing practice of high-performance networks sending communication in plaintext. We propose a security mechanism and provide metrics for analyzing both the security and performance costs.

No abstract available.

Automatic object inlining [19, 20] transforms heap data structures by fusing parent and child objects together. It can improve runtime by reducing object allocation and pointer dereference costs. We report continuing work studying object inlining optimizations. In particular, we present a new semantic derivation of the correctness conditions for object inlining, and program analysis which extends our previous work. And we present an object inlining transformation, focusing on a new algorithm which optimizes class field layout to minimize code expansion. Finally, we detail a fuller evaluation on eleven programs and libraries (including Xpdf, the 25,000 line Portable Document Format (PDF) le browser) that utilizes hardware measures of impact on the memory system. We show that our analysis scales effectively to large programs, nding many inlinable elds (45 in xpdf) at acceptable cost, and we show that, on some programs, it finds nearly all fields for which object inlining is correct, and a...

The complexity and dynamic nature of the Internet (and the emerging Computational Grid) demand that middleware and applications adapt to the changes in configuration and availability of resources. However, to the best of our knowledge there are no simulation tools which support systematic exploration of dynamic Grid software (or Grid resource) behavior. We describe our vision and initial efforts to build tools to meet these needs. Our MicroGrid simulation tools enable Globus applications to be run in arbitrary virtual grid resource environments, enabling broad experimentation. We describe the design of these tools, and their validation on micro- benchmarks, the NA parallel benchmarks, and an entire Grid application. These validation experiments show that the MicroGrid can match actual experiments within a few percent (2% to 4%).

Technology scaling of CMOS processes brings relatively faster transistors (gates) and slower interconnects (wires), making viable the addition of reconfigurability to increase performance. In the Morph/AMRM system we are exploring the addition of reconfigurable logic, deeply integrated with the processor core, employing the reconfigurability to manage the cache, datapath, and pipeline resources more effectively. However, integration of reconfigurable logic introduces significant protection and safety challenges for microprocess execution. We analyze the protection structures in a state of the art microprocessor core (R10000), identifying the few critical logic blocks and demonstrating that the majority of the logic in the processor core can be safely reconfigured. Subsequently, we propose a protection architecture for the Morph/AMRM reconfigurable processor which enable nearly the full range of power of reconfigurability in the processor core while requiring only a small number of fixed logic features which to ensure safe, protected multiprocess execution.

High-level parallel programming models supporting dynamic fine-grained threads in a global object space are becoming increasingly popular for expressing irregular applications based on sophisticated adaptive algorithms and pointer-based data structures. However, implementing these multithreaded computations on scalable parallel machines poses significant challenges, particularly with respect to object caching. Object caching techniques must be able to tolerate unresponsive processors and protocol handler occupancy delays. This paper examines whether these challenges can be offset by leveraging responsive general-purpose communication architectural features (such as remote memory access and atomic operations), possibly compensating for the lack of more sophisticated hardware primitives by relying upon increased involvement of the run-time system and the compiler. A detailed performance analysis of four irregular applications, using the Illinois Concert System on the Cray T3D and the SGI Origin 2000, finds that existing software distributed shared memory (DSM) systems are capable of delivering good performance only in the presence of a high level of responsive communication architecture support (specifically, support for remote atomic operations). Recognizing that this situation stems from the synchronous request–reply nature of DSM protocols, we present a composable object caching framework, called view caching , which exploits knowledge of application data access semantics to construct custom protocols that require reduced processor synchronization. View caching protocols are more tolerant to responsiveness and occupancy delays and are able to exploit even lower level responsive communication primitives (such as nonatomic remote memory accesses) for a performance benefit.

Global address space parallel programming models can be an effective alternative to send/receive style communication, simplifying programming or code generation and increasing performance for certain application types. Traditionally, global address space mechanisms have been implemented in hardware in order to provide the necessary communication performance and responsiveness. However new high performance cluster messaging systems now allow global address space mechanisms to be realized efficiently in software. We describe a high performance one sided communication model that is implemented as a software layer on top of the Illinois Fast Messages (FM) system. We evaluate several different software implementation architectures for the remote agent, characterizing their differing performance characteristics. Our Put/Get FM implementation achieves peak bandwidths for put/get operations of 67 MBytes/s, overheads of a few microseconds, and remote read latencies as low as 26 microseconds on a Myrinet connected PC cluster. This implementation was released publicly as part of HPVM 1.0 in August 1997, and is receiving significant usage. It has been used for an implementation of the Global Arrays library and also serves as a back-end target for PGI's commercial HPF compiler.

The authors describe their experience designing, implementing, and evaluating two generations of the high performance communication library, Fast Messages (FM) for Myrinet. In FM 1.x, they designed a simple interface and provided guarantees of reliable and in-order delivery, and flow control. While this was a significant improvement over previous systems, it was not enough. Layering MPI atop FM 1.x showed that only about 20% of the FM 1.x bandwidth could be delivered to higher level communication APIs. The second generation communication layer, FM 2.0, addresses the identified problems, providing gather-scatter, interlayer scheduling, receiver flow control, as well as some convenient API features which simplify programming. FM 2.x can deliver 70-90% to higher level APIs such as MPI. This is especially impressive as the absolute bandwidths delivered have increased nearly fourfold to 70 MB/s. They describe general issues encountered in matching two communication layers, and the solutions as embodied in FM 2.x.

Object-oriented languages such as Java and Smalltalk provide a uniform object reference model, allowing objects to be conveniently shared. If implemented directly, these uniform reference models can suffer in efficiency due to additional memory dereferences and memory management operations. Automatic inline allocation of child objects within parent objects can reduce overheads of heap-allocated pointer-referenced objects.We present three compiler analyses to identify inlinable fields by tracking accesses to heap objects. These analyses span a range from local data flow to adaptive whole-program, flow-sensitive inter-procedural analysis. We measure their cost and effectiveness on a suite of moderate-sized C++ programs (up to 30,000 lines including libraries). We show that aggressive interprocedural analysis is required to enable object inlining, and our adaptive inter-procedural analysis [23] computes precise information efficiently. Object inlining eliminates typically 40% of object accesses and allocations (improving performance up to 50%). Furthermore,

High-level parallel programming models supporting dynamic fine-grained threads in a global object space, are becoming increasingly popular for expressing irregular applications based on sophisticated adaptive algorithms and pointer-based data structures. However, implementing these multithreaded computations on scalable parallel machines poses significant challenges, particularly with respect to load-balancing. Load-balancing techniques must simultaneously incur low overhead to support fine-grained threads as well as be sophisticated enough to preserve data locality and thread execution priority. This paper presents a hierarchical framework which addresses these conflicting goals by viewing the computation as being made up of different thread subsets, each of which are load-balanced independently. In contrast to previous processor-centric approaches that have advocated the use of a uniform policy for load-balancing all threads in a computation, our framework allows each thread subset to be load-balanced using a policy most suited to its characteristics (e.g., locality or priority sensitivity). The framework consists of two parts: (i) language support which permits a programmer to tag different thread subsets with appropriate policies, and (ii) run-time support which synthesizes overall application load-balance by composing these individual policies. This framework has been implemented in the Illinois Concert runtime system, an execution platform for fine-grained concurrent object-oriented languages. Results for four large irregular applications on the Cray T3D and the SGI Origin 2000 demonstrate advantages of the hierarchical framework: performance improves by up to an order of magnitude as compared to using a uniform load-balancing policy.

Object-oriented techniques have been proffered as aids for managing complexity, enhancing reuse, and improving readability of irregular parallel applications. However, as performance is the major reason for employing parallelism, programmability and high performance must be delivered together. Using a suite of seven challenging irregular applications and the mature Illinois Concert system (a high-level concurrent object-oriented programming model) and an aggressive implementation (whole program compilation plus microsecond threading and communication primitives in the runtime), we evaluate what programming efforts are required to achieve high performance. For all seven applications, we achieve performance comparable to the best achievable via low-level programming means on large-scale parallel systems. In general, a high-level concurrent object-oriented programming model supported by aggressive implementation techniques can eliminate programmer management of many concerns – procedure and computation granularity, namespace management, and low-level concurrency management. Our study indicates that these concerns are fully automated for these applications. Decoupling these concerns makes managing the remaining fundamental concerns – data locality and load balance – much easier. In several cases, data locality and load balance for the complex algorithm and pointer data structures is automatically managed by the compiler and runtime, but in general programmer intervention was required. In a few cases, more detailed control is required, specifically explicit task priority, data consistency, and task placement. Our system integrates the expression of such information cleanly into the programming interface. Finally, only small changes to the sequential code were required to express concurrency and performance optimizations, less than 5 per cent of the source code lines were changed in all cases. This bodes well for supporting both sequential and parallel performance in a single code base. © 1998 John Wiley & Sons, Ltd.

The evaluation of advanced routing features must be based on both of costs and benefits. To date, adaptive routers have generally been evaluated on the basis of the achieved network throughput (channel utilization), ignoring the effects of implementation complexity. In this paper, we describe a parameterized cost model for router performance, characterized by two numbers: router delay and flow control time. Grounding the cost model in a 0.8 micron gate array technology, we use it to compare a number of proposed routing algorithms. From these design studies, several insights into the implementation complexity of adaptive routers are clear. First, header update and selection is expensive in adaptive routers, suggesting that absolute addressing should be reconsidered. Second, virtual channels are expensive in terms of latency and cycle time, so decisions to include them to support adaptivity or even virtual lanes should not be taken lightly. Third, requirements of larger crossbars and more complex arbitration cause some increase in the complexity of adaptive routers, but the rate of increase is small. Last, the complexity of adaptive routers significantly increases their setup delay and flow control cycle times, implying that claims of performance advantages in channel utilization and low load latency must be carefully balanced against losses in achievable implementation speed.

Programmers of concurrent applications are faced with a complex performance space in which data distribution and concurrency management exacerbate the difficulty of building large, complex applications. To address these challenges, the Illinois Concert system provides a global names-pace, implicit concurrency control and granularity management, implicit storage management, and object oriented programming features. These features are embodied in a language ICC++ (derived from C++) which has been used to build a number of kernels and applications. As high level features can potentially incur overhead, the Concert system employs a range of compiler and runtime optimization techniques to efficiently support the high level programming model. The compiler techniques include type inference, inlining and specialization; and the runtime techniques include caching, prefetching and hybrid stack/heap multithreading. The effectiveness of these techniques permits the construction of complex parallel applications that are flexible, enabling convenient application modification or tuning. We present performance results for a number of application programs which attain good speedups and absolute performance.

We propose a machine architecture that integrates programmable logic into key components of the system with the goal of customizing architectural mechanisms and policies to match an application. This approach presents an improvement over the traditional approach of exploiting programmable logic as a separate co-processor by pre-serving machine usability through software and on a traditional computer architecture by providing application-specific hardware. We present two case studies of architectural customization to enhance latency tolerance and efficiently utilize network bisection on multiprocessors for sparse matrix computations. We demonstrate that application-specific hardware and policies can provide substantial improvements in performance on a per application basis. Based on these preliminary results, we propose that an application-driven machine customization provides a promising approach to achieve high performance and combat performance fragility.

For many scalable parallel applications, the input/output (I/O) barrier rivals or exceeds that of computation and interprocessor communication. Consequently, scalable parallel secondary and tertiary storage systems are necessary to satisfy the resource demands of many national challenge problems. At present, one major challenge facing the designers of such storage systems is the wide range of I/O access patterns and the lack of general purpose file system policies that achieve high performance for variable I/O requirements. We analyze the I/O behavior of two scientific applications on the Intel Paragon XP/S. Although the two applications solve the same scientific problem and their I/O access patterns are qualitatively similar, their interactions with the file system are decidedly different. Our results show that appropriate tuning of file system policy parameters to I/O demands can significantly increase I/O throughput.

Loop tiling and communication optimization, such as message pipelining and aggregation, can achieve optimized and robust memory performance by proactively managing storage and data movement. In this paper, we generalize these techniques to pointer-based data structures (PBDSs). Our approach, dynamic pointer alignment (DPA), has two components. The compiler decomposes a program into non-blocking threads that operate on specific pointers and labels thread creation sites with their corresponding pointers. At runtime, an explicit mapping from pointers to dependent threads is updated at thread creation and is used to dynamically schedule both threads and communication, such that threads using the same objects execute together, communication overlaps with local work, and messages are aggregated. We have implemented DPA to optimize remote reads to global PBDSs on parallel machines. Our empirical results on the force computation phases of two applications that use sophisticated PBDSs, Barnes-Hut and FMM, show that DPA achieves good absolute performance and speedups by enabling tiling and communication optimization on the CRAY T3D.

FM-QoS employs a novel communication architecture based on network feedback to provide predictable communication performance (e.g. deterministic latencies and guaranteed bandwidths) for high speed cluster interconnects. Network feedback is combined with self-synchronizing communication schedules to achieve synchrony in the network interfaces (NIs). Based on this synchrony, the network can be scheduled to provide predictable performance without special network QoS hardware. We describe the key element of the FM-QoS approach, feedback-based synchronization (FBS), which exploits network feedback to synchronize senders. We use Petri nets to characterize the set of self-synchronizing communication schedules for which FBS is effective and to describe the resulting synchronization overhead as a function of the clock drift across the network nodes. Analytic modeling suggests that for clocks of quality 300 ppm (such as found in the Myrinet NI), a synchronization overhead less than 1% of the total communication traffic is achievable -- significantly better than previous software-based schemes and comparable to hardware-intensive approaches such as virtual circuits (e.g. ATM). We have built a prototype of FBS for Myricom s Myrinet network (a 1.28 Gbps cluster network) which demonstrates the viability of the approach by sharing network resources with predictable performance. The prototype, which implements the local node schedule in software, achieves predictable latencies of 23 µs for a single-switch, 8-node network and 2 KB packets. In comparison, the best-effort scheme achieves 104 µs for the same network without FBS. While this ratio of over four to one already demonstrates the viability of the approach, it includes nearly 10 µs of overhead due to the software implementation. For hardware implementations of local node scheduling, and for networks with cascaded switches, these ratios should be much larger factors.

Compressionless routing (CR) is an adaptive routing framework which provides a unified framework for efficient deadlock free adaptive routing and fault tolerance. CR exploits the tight coupling between wormhole routers for flow control to detect and recover from potential deadlock situations. Fault tolerant compressionless routing (FCR) extends CR to support end to end fault tolerant delivery. Detailed routing algorithms, implementation complexity, and performance simulation results for CR and FCR are presented. These results show that the hardware for CR and FCR networks is modest. Further, CR and FCR networks can achieve superior performance to alternatives such as dimension order routing. Compressionless routing has several key advantages: deadlock free adaptive routing in toroidal networks with no virtual channels, simple router designs, order preserving message transmission, applicability to a wide variety of network topologies, and elimination of the need for buffer allocation messages. Fault tolerant compressionless routing has several additional advantages: data integrity in the presence of transient faults (nonstop fault tolerance), permanent fault tolerance, and elimination of the need for software buffering and retry for reliability. The advantages of CR and FCR not only simplify hardware support for adaptive routing and fault tolerance, they also can simplify software communication layers.

The modest I/O configurations and file system limitations of many current high-performance systems preclude solution of problems with large I/O needs. I/O hardware and file system parallelism is the key to achieving high performance. We analyze the I/O behavior of several versions of two scientific applications on the Intel Paragon XP/S. The versions involve incremental application code enhancements across multiple releases of the operating system. Studying the evolution of I/O access patterns underscores the interplay between application access patterns and file system features. Our results show that both small and large request sizes are common, that at present, application developers must manually aggregate small requests to obtain high disk transfer rates, that concurrent file accesses are frequent, and that appropriate matching of the application access pattern and the file system access mode can significantly increase application I/O performance. Based on these results, we describe a set of file system design principles.

Network service guarantees not only provide significant performance benefits to distributed computing systems (more balanced resource utilization, fast fault recovery, and fair network access), but they are also essential for many new applications requiring real-time communications with continuous data types (audio/video). Most existing algorithms which provide network service guarantees are too complicated to be feasible in high-speed, low-cost switches for multicomputer networks. The simpler algorithms proposed provide only limited service guarantees or waste significant network resources.We present a novel, cost-effective queueing and scheduling algorithm, called Rotating Combined Queueing (RCQ), which can efficient]y support a range of service guarantees including deterministic delay bounds and bandwidth guarantees in multicomputer networks. By allowing bursty traffic to utilize unused network resources efficiently, RCQ also can provide competitive performance to best-effort data communications. Such cost-effective service guarantees not only provide substantial benefits to the overall system performance, but can also further expand the domain of multicomputer applications to encompass distributed multimedia applications requiring isochronous communications.

Article Free Access Share on PPFS: a high performance portable parallel file system Authors: James V. Huber Department of Computer Science, University of Illinois, Urbana, Illinois Department of Computer Science, University of Illinois, Urbana, IllinoisView Profile , Andrew A. Chien Department of Computer Science, University of Illinois, Urbana, Illinois Department of Computer Science, University of Illinois, Urbana, IllinoisView Profile , Christopher L. Elford Department of Computer Science, University of Illinois, Urbana, Illinois Department of Computer Science, University of Illinois, Urbana, IllinoisView Profile , David S. Blumenthal Department of Computer Science, University of Illinois, Urbana, Illinois Department of Computer Science, University of Illinois, Urbana, IllinoisView Profile , Daniel A. Reed Department of Computer Science, University of Illinois, Urbana, Illinois Department of Computer Science, University of Illinois, Urbana, IllinoisView Profile Authors Info & Claims ICS '95: Proceedings of the 9th international conference on SupercomputingJuly 1995 Pages 385–394https://doi.org/10.1145/224538.224638Online:03 July 1995Publication History 127citation614DownloadsMetricsTotal Citations127Total Downloads614Last 12 Months18Last 6 weeks5 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 SiteeReaderPDF

Programming models based on messaging continue to be an important programming model for parallel machines. Messaging costs are strongly influenced by a machine's network interface architecture. We examine the impact of architectural support for messaging in two machines --- the TMC CM-5 and the Cray T3D --- by exploring the design and performance of several messaging implementations. The additional features in the T3D support remote operations: memory access, fetch-and-increment, atomic swaps, and prefetch.Experiments on the CM-5 show that requiring processor involvement for message reception can increase the communication overheads from 60% to 300% for moderate variations in computation grain size at the destination. In contrast, the T3D hardware for remote operations decouples message reception from processor activity, producing high-performance messaging independent of computation grain size or variability.In addition, hardware support for a shared address space in the T3D can be used to solve the output contention problem (output hot spots), producing messaging implementations that are robust over a wide variety of traffic patterns. Atomic swap hardware can be used to build a distributed message queue, enabling a "pull" messaging scheme where the destination requests data transfer upon receive. This scheme uses prefetches to mask receive latency. While this yields performance robust over output contention, its base cost is competitive only for small messages (up to 64 bytes) because of the high cost of issuing and resolving prefetches in the T3D. Emulation shows that if the interaction costs can be reduced by a factor of eight (250ns to 31ns), perhaps by moving the prefetch queue on chip, and there is a corresponding increase in the prefetch queue size, the pull scheme can give superior performance in all eases.

Concurrent object-oriented programming (COOP) languages focus the abstraction and encapsulation power of abstract data types on the problem of concurrency control. In particular, pure fine-grained concurrent object-oriented languages (as opposed to hybrid or data parallel) provides the programmer with a simple, uniform, and flexible model while exposing maximum concurrency. While such languages promise to greatly reduce the complexity of large-scale concurrent programming, the popularity of these languages has been hampered by efficiency which is often many orders of magnitude less than that of comparable sequential code. We present a sufficiency set of techniques which enables the efficiency of fine-grained concurrent object-oriented languages to equal that of traditional sequential languages (like C) when the required data is available. These techniques are empirically validated by the application to a COOP implementation of the Livermore Loops.

Rapid increases in computing and communication performance are exacerbating the long-standing problem of performance-limited input/output. Indeed, for many otherwise scalable parallel applications. input/output is emerging as a major performance bottleneck. The design of scalable input/output systems depends critically on the input/output requirements and access patterns for this emerging class of large-scale parallel applications. However, hard data on the behavior of such applications is only now becoming available. In this paper, we describe the input-output requirements of three scalable parallel applications (electron scattering, terrain rendering, and quantum chemistry, on the Intel Paragon XP/S. As part of an ongoing parallel input/output characterization effort, we used instrumented versions of the application codes to capture and analyze input/output volume, request size distributions, and temporal request structure. Because complete traces of individual application input/output requests were captured, in-depth, off-line analyses were possible. In addition, we conducted informal interviews of the application developers to understand the relation between the codes' current and desired input/output structure. The results of our studies show a wide variety of temporal and spatial access patterns, including highly read-intensive and write-intensive phases, extremely large and extremely small request sizes, and both sequential and highly irregular access patterns. We conclude with a discussion of the broad spectrum of access patterns and their profound implications for parallel file caching and prefetching schemes.

While fine-grained concurrent languages can naturally capture concurrency in many irregular and dynamic problems, their flexibility has generally resulted in poor execution effciency. In such languages the computation consists of many small threads which are created dynamically and synchronized implicitly. In order to minimize the overhead of these operations, we propose a hybrid execution model which dynamically adapts to runtime data layout, providing both sequential efficiency and low overhead parallel execution. This model uses separately optimized sequential and parallel versions of code. Sequential efficiency is obtained by dynamically coalescing threads via stack-based execution and parallel efficiency through latency hiding and cheap synchronization using heap-allocated activation frames. Novel aspects of the stack mechanism include handling return values for futures and executing forwarded messages (the responsibility to reply is passed along, like call/cc in Scheme) on the stack. In addition, the hybrid execution model is expressed entirely in C, and therefore is easily portable to many systems. Experiments with function-call intensive programs show that this model achieves sequential efficiency comparable to C programs. Experiments with regular and irregular application kernels on the CM5 and T3D demonstrate that it can yield 1.5to 3 times better performance than code optimized for parallel execution alone.

Network throughput can be increased by allowing multipath, adaptive routing. Adaptive routing allows more freedom in the paths taken by messages, spreading load over physical channels more evenly. The flexibility of adaptive routing introduces new possibilities of deadlock. Previous deadlock avoidance schemes in k -ary n -cubes require an exponential number of virtual channels. We describe a family of deadlock-free routing algorithms, called planar-adaptive routing algorithms, that require only a constant number of virtual channels, independent of networks size and dimension. Planar-adaptive routing algorithms reduce the complexity of deadlock prevention by reducing the number of choices at each routing step. In the fault-free case, planar-adaptive networks are guaranteed to be deadlock-free. In the presence of network faults, the planar-adaptive router can be extended with misrouting to produce a working network which remains provably deadlock free and is provably livelock free. In addition, planar-adaptive networks can simultaneously support both in-order and adaptive, out-of-order packet delivery. Planar-adaptive routing is of practical significance. It provides the simplest known support for deadlock-free adaptive routing in k -ary n -cubes of more than two dimensions (with k >2). Restricting adaptivity reduces the hardware complexity, improving router speed or allowing additional performance-enhancing network features. The structure of planar-adaptive routers is amenable to efficient implementation. Simulation studies show that planar-adaptive routers can increase the robustness of network throughput for nonuniform communication patterns. Planar-adaptive routers outperform deterministic routers with equal hardware resources. Further, adding virtual lanes to planar-adaptive routers increases this advantage. Comparisons with fully adaptive routers show that planar-adaptive routers, limited adaptive routers, can give superior performance. These results indicate the best way to allocate router resources to combine adaptivity and virtual lanes. Planar-adaptive routers are a special case of limited adaptivity routers. We define a class of adaptive routers with f degrees of routing freedom. This class, termed f-flat adaptive routers , allows a direct cost-performance tradeoff between implementation cost (speed and silicon area) and routing freedom (channel utilization). For a network of a particular dimension, the cost of adaptivity grows linearly with the routing freedom. However, the rate of growth is a much larger constant for high-dimensional networks. All of the properties proven for planar-adaptive routers, such as deadlock and livelock freedom, also apply to f -flat adaptive routers.

Despite improvements in network interfaces and software messaging layers, software communication overhead still dominates the hardware routing cost in most systems. In this study, we identify the sources of this overhead by analyzing software costs of typical communication protocols built atop the active messages layer on the CM-5. We show that up to 50–70% of the software messaging costs are a direct consequence of the gap between specific network features such as arbitrary delivery order, finite buffering, and limited fault-handling, and the user communication requirements of in-order delivery, end-to-end flow control, and reliable transmission. However, virtually all of these costs can be eliminated if routing networks provide higher-level services such as in-order delivery, end-to-end flow control, and packet-level fault-tolerance. We conclude that significant cost reductions require changing the constraints on messaging layers: we propose designing networks and network interfaces which simplify or replace software for implementing user communication requirements.

Compressionless Routing (CR) is a new adaptive routing framework which provides a unified framework for efficient deadlock-free adaptive routing and fault-tolerance. CR exploits the tight-coupling between wormhole routers for flow control to detect potential deadlock situations and recover from them. Fault-tolerant Compressionless Routing (FCR) extends Compressionless Routing to support end-to-end fault-tolerant delivery. Detailed routing algorithms, implementation complexity and performance simulation results for CR and FCR are presented. CR has the following advantages: deadlock-free adaptive routing in torus networks with no virtual channels, simple router designs, order-preserving message transmission, applicability to a wide variety of network topologies, and elimination of the need for buffer allocation messages. FCR has the following advantages: tolerates transient faults while maintaining data integrity (nonstop fault-tolerance), tolerates permanent faults, can be applied to a wide variety of network topologies, and eliminates the need for software buffering and retry for reliability. These advantages of CR and FCR not only simplify hardware support for adaptive routing and fault-tolerance, they also can simplify communication software layers.>

Concrete type information is invaluable for program optimization. The determination of concrete types in object-oriented languages is a flow sensitive global data flow problem. It is made difficult by dynamic dispatch (virtual function invocation) and first class functions (and selectors)—the very program structures for whose optimization its results are most critical. Previous work has shown that constraint-based type inference systems can be used to safely approximate concrete types [15], but their use can be expensive and their results imprecise.

Inefficient implementations of global namespaces, message passing, and thread scheduling on stock multicomputers have prevented concurrent object-oriented programming (COOP) languages from gaining widespread acceptance.Recognizing that the architectures of stock m[ilticomputers impose a hierarchy of costs for these operations, we have described a runtime system which provides different versions of each primitive, exposing performance distinctions for optimization.We confirm the advantages of a cost-hierarchy based runtirne system organization by showing a variation of two orders of magnitude in version costs for a CM5 implementation.Frequency measurements based on COOP application programs demonstrate that a 39% invocation cost reduction is feasible by simply se[ecting cheaper versions of runtime operations.

A description is given of the Message-Driven Processor (MDP), an integrated multicomputer node. It incorporates a 36-bit integer processor, a memory management unit, a router for a 3D mesh network, a network interface, a 4K*36-bit word static RAM (SRAM), and an ECC dynamic RAM (DRAM) controller on a single 1.1 M-transistor VLSI chip. The MDP is not specialized for a single model of computation. Instead, it incorporates efficient primitive mechanisms for communication, synchronization, and naming. These mechanisms support most proposed parallel programming models. Each processing node of the MIT J-Machine consists of an MDP with 1 Mbit of DRAM.>

Network throughput can be increased by allowing multipath, adaptive routing. Adaptive routing allows more freedom in the paths taken by messages, spreading load over physical channels more evenly. The flexibility of adaptive routing introduces new possibilities of deadlock. Previous deadlock avoidance schemes in k-ary n-cubes require an exponential number of virtual channels, independent of network size and dimension. Planar adaptive routing algorithms reduce the complexity of deadlock prevention by reducing the number of choices at each routing step. In the fault-free case, planar-adaptive networks are guaranteed to be deadlock-free. In the presence of network faults, the planar-adaptive router can be extended with misrouting to produce a working network which remains provably deadlock free and is provably livelock free. In addition, planar adaptive networks can simultaneously support both in-order and adaptive, out-of-order packet delivery.

To program massively concurrent MIMD machines, programmers need tools for managing complexity.One important tool that has been used in the sequential programming world is hierarchies of abstractions.Unfortunately, most concurrent object-oriented languages construct hierarchical abstractions from objects that serialize -serializing the abstractions.In machines with tens of thousands of processors, unnecessary serialization of this sort can cause significant loss of concurrency.Concurrent Aggregates (CA) is an object-oriented language that allows programmers to build unserialized hierarchies of abstractions by using aggregates.An aggregate in CA is a homogeneous collection of objects (called representatives) that are grouped together and may be referenced by a single aggregate name.Aggregates are integrated into the object model, allowing them to be used wherever an object could be used.Concurrent Aggregates also incorporates several innovative language features that facilitate programming with aggregates.Intra-aggregate addressing aids cooperation between parts of an aggregate.Delegation allows programmers to compose an concurrent aggregate behavior from a number of objects or aggregates.Messages in CA are first class objects that can be used to create message handling abstractions (they handle messages as data).Such abstractions facilitate concurrent operations on aggregates.Continuations are also first class objects.In addition, programmers can construct continuations and use them just like system continuations.User constructed continuations can implement synchronization structures such as a barrier synchronization.

CST is a programming language based on Smalltalk-802 that supports concurrency using locks, asynchronous messages, and distributed objects. In this paper, we describe CST: the language and its implementation. Example programs and initial programming experience with CST are described. Our implementation of CST generates native code for the J-machine, a fine-grained concurrent computer. Some compiler optimizations developed in conjunction with that implementation are also described.

We propose a machine architecture for a high-performance processing node for a message-passing, MIMD concurrent computer. The principal mechanisms for attaining this goal are the direct execution and buffering of messages and a memory-based architecture that permits very fast context switches. Our architecture also includes a novel memory organization that permits both indexed and associative accesses and that incorporates an instruction buffer and message queue. Simulation results suggest that this architecture reduces message reception overhead by more than an order of magnitude.