The growth rate of the GPU memory capacity has not been able to keep up with that of the size of large language models (LLMs), hindering the model training process. In particular, activations-the intermediate tensors produced during forward propagation and reused in backward propagation-dominate the GPU memory use. This leads to high training overheads such as expensive weight update costs due to the small micro-batch size. To address this challenge, we propose SSDTrain, an adaptive activation offloading framework to high-capacity NVMe SSDs. SSDTrain reduces GPU memory usage without impacting performance by fully overlapping data transfers with computation. SSDTrain is compatible with popular deep learning frameworks like PyTorch, Megatron, and DeepSpeed, and it employs techniques such as tensor deduplication and forwarding to further enhance efficiency. We extensively experimented with popular LLMs like GPT, BERT, and T5. Results demonstrate that SSDTrain reduces 47% of the activation peak memory usage. At the same time, SSDTrain perfectly overlaps the I/O with the computation and incurs negligible overhead. Compared with keeping activations in GPU memory and layerwise full recomputation, SSDTrain achieves the best memory savings with negligible throughput loss. We further analyze how the reduced activation memory use may be leveraged to increase throughput by increasing micro-batch size and reducing pipeline parallelism bubbles.

One of the challenges in a viral pandemic is the emergence of novel variants with different phenotypical characteristics. An ability to forecast future viral individuals at the sequence level enables advance preparation by characterizing the sequences and closing vulnerabilities in current preventative and therapeutic methods. In this article, we explore, in the context of a viral pandemic, the problem of generating complete instances of undiscovered viral protein sequences, which have a high likelihood of being discovered in the future using protein language models. Current approaches to training these models fit model parameters to a known sequence set, which does not suit pandemic forecasting as future sequences differ from known sequences in some respects. To address this, we develop a novel method, called PandoGen, to train protein language models towards the pandemic protein forecasting task. PandoGen combines techniques such as synthetic data generation, conditional sequence generation, and reward-based learning, enabling the model to forecast future sequences, with a high propensity to spread. Applying our method to modeling the SARS-CoV-2 Spike protein sequence, we find empirically that our model forecasts twice as many novel sequences with five times the case counts compared to a model that is 30× larger. Our method forecasts unseen lineages months in advance, whereas models 4× and 30× larger forecast almost no new lineages. When trained on data available up to a month before the onset of important Variants of Concern, our method consistently forecasts sequences belonging to those variants within tight sequence budgets.

We developed a set of tools designed to provide rapid feedback to students as they learn to write programs in assembly language (LC-3, a RISC-like educational instruction set architecture). At the heart of the system is an extended version of KLEE, KLC3, that enables us to both identify issues and perform equivalence checking between student code and a gold (correct) version of each assignment. Feedback begins when students edit their code using a VSCode extension that leverages static analysis to perform a variety of correctness and style checks, encouraging students to improve their code quality. Each time a student commits code to their Git repository, our system triggers. Using KLC3 (KLEE), the student code is executed along with the gold version, and issues and behavioral differences are delivered back to the student through their Git repository as a human-readable report, test cases, and scripts. A queueing system allows students to monitor progress, but responses are generally available within minutes. We also extended the LC-3 simulation tools to support reverse debugging, making the process of finding complex bugs much more tractable for students, and used Emscripten to develop a browser-based interface for use in testing and debugging. Finally, our system maintains an individual regression test suite for each student and requires a submission to pass all previous tests before re-evaluation in KLC3, thus avoiding encouraging programming-by-guesswork. We deployed the system to provide feedback for the assembly programming assignments in a class of over 100 students in Fall 2020. Students wrote a median of around 700 lines of assembly for these assignments, making heavy use of our tools to understand and eliminate their bugs. Anonymous student feedback on the tools was uniformly positive. Since that semester, we have continued to refine and expand our tools’ analysis capabilities and performance, and plan to deploy the system again in the near future (the class is offered every Fall).

BACKGROUND: Modern Next Generation- and Third Generation- Sequencing methods such as Illumina and PacBio Circular Consensus Sequencing platforms provide accurate sequencing data. Parallel developments in Deep Learning have enabled the application of Deep Neural Networks to variant calling, surpassing the accuracy of classical approaches in many settings. DeepVariant, arguably the most popular among such methods, transforms the problem of variant calling into one of image recognition where a Deep Neural Network analyzes sequencing data that is formatted as images, achieving high accuracy. In this paper, we explore an alternative approach to designing Deep Neural Networks for variant calling, where we use meticulously designed Deep Neural Network architectures and customized variant inference functions that account for the underlying nature of sequencing data instead of converting the problem to one of image recognition. RESULTS: Results from 27 whole-genome variant calling experiments spanning Illumina, PacBio and hybrid Illumina-PacBio settings suggest that our method allows vastly smaller Deep Neural Networks to outperform the Inception-v3 architecture used in DeepVariant for indel and substitution-type variant calls. For example, our method reduces the number of indel call errors by up to 18%, 55% and 65% for Illumina, PacBio and hybrid Illumina-PacBio variant calling respectively, compared to a similarly trained DeepVariant pipeline. In these cases, our models are between 7 and 14 times smaller. CONCLUSIONS: We believe that the improved accuracy and problem-specific customization of our models will enable more accurate pipelines and further method development in the field. HELLO is available at https://github.com/anands-repo/hello.

While the Hidden Markov Model (HMM) is a versatile generative model of sequences capable of performing many exact inferences efficiently, it is not suited for capturing complex long-term structure in the data. Advanced state-space models based on Deep Neural Networks (DNN) overcome this limitation but cannot perform exact inferences. In this article, we present a new generative model for sequences that combines both aspects, the ability to perform exact inferences and the ability to model long-term structure, by augmenting the HMM with a deterministic, continuous state variable modeled through a Recurrent Neural Network. We empirically study the performance of the model on (i) synthetic data comparing it to the HMM, (ii) a supervised learning task in bioinformatics where it outperforms two DNN-based regressors and (iii) in the generative modeling of music where it outperforms many prominent DNN-based generative models.

The proliferation of high-throughput sequencing machines ensures rapid generation of up to billions of short nucleotide fragments in a short period of time. This massive amount of sequence data can quickly overwhelm today's storage and compute infrastructure. This paper explores the use of hardware acceleration to significantly improve the runtime of short-read alignment, a crucial step in preprocessing sequenced genomes. We focus on the Levenshtein distance (edit-distance) computation kernel and propose the ASAP accelerator, which utilizes the intrinsic delay of circuits for edit-distance computation elements as a proxy for computation. Our design is implemented on an Xilinx Virtex 7 FPGA in an IBM POWER8 system that uses the CAPI interface for cache coherence across the CPU and FPGA. Our design is$200\times$faster than an equivalent Smith-Waterman-C implementation of the kernel running on the host processor,$40-60\times$faster than an equivalent Landau-Vishkin-C++ implementation of the kernel running on the IBM Power8 host processor, and$2\times$faster for an end-to-end alignment tool for 120–150 base-pair short-read sequences. Further the design represents a$3760\times$improvement over the CPU in performance/Watt terms.

High-throughput techniques have revolutionized the study of genomics and molecular biology in recent years. These methods provide a large quantity of sequence data, and have applications in different areas of bioinformatics. One can sequence parts or whole of an organism's DNA to determine genetic information about an individual or a population, measure expression levels of different genes under different conditions, and determine binding affinity of proteins to DNA segments revealing details regarding gene regulation, at a higher resolution than before. However, different high-throughput methods that target even a single application have different underlying error models. Robust analytic pipelines are necessary to extract necessary information from the raw data. In this paper, we discuss future research directions for developing such analytics using techniques from Machine Learning and Deep Neural Networks. We focus on two applications that will affect the diagnosis and treatment of cancer.

No abstract available.

Path explosion has been a problem for symbolic execution for a long time. The key to avoid path explosion is to limit the number of paths generated within loops while maintaining high code coverage. Full symbolic execution creates paths for every possible execution path. Frequently, paths within loops do not contribute to code coverage. Branches within loops may generate new states at every iteration. The path explosion problem created by loops often stops symbolic execution to reach deeper parts of the code.

This paper explores hardware acceleration to significantly improve the runtime of computing the forward algorithm on Pair-HMM models, a crucial step in analyzing mutations in sequenced genomes. We describe 1) the design and evaluation of a novel accelerator architecture that can efficiently process real sequence data without performing wasteful work; and 2) aggressive memoization techniques that can significantly reduce the number of invocations of, and the amount of data transferred to the accelerator. We describe our demonstration of the design on a Xilinx Virtex 7 FPGA in an IBM Power8 system. Our design achieves a 14.85× higher throughput than an 8-core CPU baseline (that uses SIMD and multi-threading) and a 147.49 × improvement in throughput per unit of energy expended on the NA12878 sample.

Using automated grading tools to provide feedback to students is common in Computer Science education. The first step of automated grading is to find defects in the student program. However, finding bugs in code has never been easy. Comparing computation results using a fixed set of test cases is still the most common way to determine correctness among current automated grading tools. It takes time and effort to design a good set of test cases that can test the student code thoroughly. In practice, tests used for grading are often insufficient for accurate diagnosis.

With heterogeneous computing on the rise, executing programs efficiently on different devices from a single source code has become increasingly important. OpenCL, having a bulk-synchronous programming model, has been proposed as a framework for writing such performance-portable programs. Execution order of work-items in a program is unconstrained except at barrier synchronization events, giving some freedom to an implementation when scheduling work-items between synchronization points. Many OpenCL (and CUDA) compilers have been designed for targeting multicore CPU architectures. However, scheduling work-items in prior work has been done with primary focus on correctness and vectorization. To the best of our knowledge, no existing implementations consider the impact of work-item scheduling on data locality. We propose an OpenCL compiler that performs data-locality-centric work-item scheduling. By analyzing the memory addresses accessed in loops within a kernel, our technique can make better decisions on how to schedule work-items to construct better memory access patterns, thereby improving performance. Our approach achieves geomean speedups of 3.32× over AMD's and 1.71 × over Intel's implementations on Parboil and Rodinia benchmarks.

Currently, GPUs and data parallel processors leverage latency tolerance techniques such as multithreading and prefetching to maximize performance per Watt. However, choosing a technique that provides energy-efficiency on a wide variety of workloads is difficult, as the type of latency to tolerate, required hardware complexity, and energy consumption is directly related to application behavior. After qualitatively evaluating five commonly used latency tolerance techniques, we develop a hybrid technique utilizing multithreading and decoupled execution to maximize performance while minimizing hardware complexity and energy consumption across a wide variety of workloads. We compare our hybrid technique with the five commonly used techniques on a 1024-core data parallel processor by performing a comprehensive design space exploration, leveraging detailed performance and physical design models. By intelligently leveraging both decoupled execution and multithreading, our hybrid latency tolerance technique is able to improve energy-efficiency by 28% to 89% over any single technique on data parallel benchmarks. Compared to other combinations of latency tolerance techniques, we find that our hybrid latency tolerance technique provides the highest energy-efficiency by over 26%.

Future CMPs will combine many simple cores with deep cache hierarchies. With more cores, cache resources per core are fewer, and must be shared carefully to avoid poor utilization due to conflicts and pollution. Explicit motion of data in these architectures, such as message passing, can provide hints about program behavior that can be used to hide latency and improve cache behavior. However, to make these models attractive, synchronization overhead and data copying must also be offloaded from the processors. In this paper, we describe a Message Orchestration and Performance Enhancement Device (MOPED) that provides hardware mechanisms to support state-of-the-art message passing protocols such as MPI. MOPED extends the per-processor cache controllers and coherence protocol to support message synchronization and management in hardware, to transfer message data efficiently without intermediate buffer copies, and to place useful data in caches in a timely manner. MOPED thus allows full overlap between communication and computation on the cores. We extended a 16-core full-system simulator based on Simics and FeS2. MOPED interacts with the directory controllers to orchestrate message data. We evaluated benefits to performance and coherence traffic by integrating MOPED into the MPICH runtime. Relative to unmodified MPI execution, MOPED reduces execution time of real applications (NAS Parallel Benchmarks) by 17-45% and of communication microbenchmarks (Intel's IMB) by 76-94%. Off-chip memory misses are reduced by 43-88% for applications and by 75-100% for microbenchmarks.

Optical backbone networks are becoming increasingly intelligent and flexible. These networks are able to establish high-bandwidth wavelength connections on-demand to support future network-centric applications. Choosing an efficient path in a timely manner, while considering important criteria such as operation costs and network performance, is a key problem confronting the network operators. Subtle path preferences of different dynamic routing algorithms (which are usually ignored by traditional analysis techniques) can make a significant difference in performance on mesh networks. It opens new research to advance routing algorithms in both analysis and implementation paradigms. In this paper, we propose an opportunity cost model that provides fast and accurate analysis for threshold-based online congestion-aware routing algorithms. The model is simple to compute, robust to different network topologies, and scalable. We show that our model further aids in the design of a number of new routing algorithms that can be easily applied to practical networks. In contrast to previous work, the optimal threshold values for our algorithms can be identified analytically, and the values sustain good performance on different network topologies and sizes.

In this paper, we evaluate a set of coherence architectures in the context of a 1024-core chip multiprocessor (CMP) tailored to throughput-oriented parallel workloads. Based on our analysis, we develop and evaluate two techniques for scaling coherence to thousand-core CMPs. We find that a broadcast-based probe filtering scheme provides reasonable performance up to 128 cores for some benchmarks, but is not generally scalable. We propose a broadcast-collective network for accelerating probe filter misses, which extends scalability but falls short of supporting 1024 cores. We find that a sparse directory with an invalidate-on-evict policy can work well for many throughput-oriented workloads. However, the on-die structures required to achieve good performance carry a large performance and power overhead. To achieve thousand-core scalability with smaller and less associative sparse directories, we introduce WayPoint, a mechanism that increases directory associativity and capacity dynamically. Using less than 3% of total die area, Way-Point achieves performance within 4% of an infinitely large on-die directory.

Traditional backbone optical networks can take months to provision a wavelength connection. Future optical networking aims at reducing the provisioning time to a few minutes. In conjunction, new services that allow the customers to dynamically set up and take down their connections is emerging. In this paper, we introduce the problem of optimizing network resources on a reconfigurable optical backbone network that provides such dynamic optical services. The problem grows exponentially in network scale and customer's demands, thus solving the entire problem for a realistic network is impractical. We address this problem by developing a heuristic optimization procedure, combined with problem-size reduction techniques. We show that good results can be achieved using small amounts of computing power and that our solutions are within 11% of a lower bound.

Two broad classes of memory models are available today: models with hardware cache coherence, used in conventional chip multiprocessors, and models that rely upon software to manage coherence, found in compute accelerators. In some systems, both types of models are supported using disjoint address spaces and/or physical memories. In this paper we present Cohesion, a hybrid memory model that enables fine-grained temporal reassignment of data between hardware-managed and software-managed coherence domains, allowing a system to support both. Cohesion can be used to dynamically adapt to the sharing needs of both applications and runtimes. Cohesion requires neither copy operations nor multiple address spaces.

This paper presents a task-centric memory model for 1000-core compute accelerators. Visual computing applications are emerging as an important class of workloads that can exploit 1000-core processors. In these workloads, we observe data sharing and communication patterns that can be leveraged in the design of memory systems for future 1000-core processors. Based on these insights, we propose a memory model that uses a software protocol, working in collaboration with hardware caches, to maintain a coherent, single-address space view of memory without the need for hardware coherence support. We evaluate the task-centric memory model in simulation on a 1024-core MIMD accelerator we are developing that, with the help of a runtime system, implements the proposed memory model. We evaluate coherence management policies related to the task-centric memory model and show that the overhead of maintaining a coherent view of memory in software can be minimal. We further show that, while software management may constrain speculative hardware prefetching into local caches, a common optimization, it does not constrain the more relevant use case of off-chip prefetching from DRAM into shared caches.

This paper considers Rigel, a programmable accelerator architecture for a broad class of data- and task-parallel computation. Rigel comprises 1000+ hierarchically-organized cores that use a fine-grained, dynamically scheduled single-program, multiple-data (SPMD) execution model. Rigel's low-level programming interface adopts a single global address space model where parallel work is expressed in a task-centric, bulk-synchronized manner using minimal hardware support. Compared to existing accelerators, which contain domain-specific hardware, specialized memories, and/or restrictive programming models, Rigel is more flexible and provides a straightforward target for a broader set of applications.

As physical layer impairments play a large role in determining the ultimate performance of all-optical networks, it has attracted much attention. However, traditional survivability schemes have been designed and utilized without considering the quality of transmission at the physical layer. Recently, a few studies on QoT-aware (quality of transmission) protection were initiated to meet the reliability needs of future communications infrastructures. In this paper, we present a study of how transmission impairments caused by non-ideal characteristics of network components (such as amplifier spontaneous emission noise and crosstalk) affect the survivability under various QoT-aware protection schemes. We present heuristic QoT-guaranteed protection RWA for dynamic provisioning that forgoes multiple bit-error-rate calculations, and quantify the performance of various QoT-aware schemes. We also evaluate the tradeoff between using crosstalk-free Banyan switches and utilizing switch plane selection with non-crosstalk-free designs. It is expensive to provide QoT-guaranteed protection, but the usefulness of QoT-aware (nonguaranteed) schemes, while cost-effective, depends on the topology. Our results also show that QoT-unaware algorithms, while performing significantly worse in terms of blocking, can have slightly better post-failure performance.

We present HybridOS, a set of operating system extensions for supporting fine-grained reconfigurable accelerators integrated with general-purpose computing platforms. HybridOS specifically targets the application integration, data movement and communication overheads for a CPU/accelerator model when running a commodity operating system. HybridOS provides a simple API for applications and a well-defined hardware interface for reconfigurable accelerators. The goal is to reduce the difficulty in mapping applications into a CPU/accelerator model compared to an unrestrained FPGA platform while achieving whole-application speedups. HybridOS is integrated into a full Linux distribution running on the embedded processor of an FPGA. Application-specific accelerators are implemented in the reconfigurable fabric of the FPGA that are allocated to user applications running on Linux. We have developed and evaluated four methods for accessing the data buffers required by hardware-accelerated applications using our prototype. The results of our work show the feasibility of our system for a case study, JPEG encoding with two accelerators, and an evaluation of HybridOS for varying data movement requirements that can be used as a guide for future applications developers

Data-parallel co-processors have the potential to improve performance in highly parallel regions of code when coupled to a general-purpose CPU. However, applications often have to be modified in non-intuitive and complicated ways to mitigate the cost of data marshalling between the CPU and the co-processor. In some applications the overheads cannot be amortized and co-processors are unable to provide benefit. The additional effort and complexity of incorporating co-processors makes it difficult, if not impossible, to effectively utilize co-processors in large applications.

Network dimensioning for wavelength-routed WDM networks has been extensively studied to maximize connection acceptance rate while minimizing the total cost. However, Internet services are increasingly generating more demands that have high-bandwidth requirements with relatively short holding times. As globalization of companies or organizations becomes a new trend, the variety of Internet service demands, in space and time, creates a more variable and unpredictable traffic model for long term network provisioning. At the same time, upgrading backbone networks remains expensive and infrequent. It is important to be able to efficiently utilize precious network resources so that low call blocking is achieved while requiring fewer upgrades when the traffic model changes. There are two kinds of dimensioning problems. First, basic dimensioning allocates network resources for a newly built network. Second, incremental dimensioning allocates extra resources for an already built network without affecting currently available resources. Historically, routing and dimensioning problems are studied together as an optimization problem. However, as integrating multiple network layers into one control platform becomes a common trend, and as higher-layer traffic that currently utilize dynamic routing imposed on logical layers increases, it is essential to plan the underlying network based on dynamic routing schemes, such as open shortest path routing (SPF). In this paper, we study basic and incremental dimensioning for dynamic routed traffic. We propose a simulation based basic dimensioning approach and introduce two new incremental dimensioning techniques: MEAN and SD. We also introduce an evolutionary traffic model and traffic load computation criteria. Simulation results show that basic dimensioning effectively reduces the topological bottlenecks, rendering 7% less blocking compared to uniform allocation. With the evolutionary traffic model, SD incremental dimensioning shows advantages over the MEAN method on most practical networks. We also compare our results with fixed routing and dimensioning approaches, showing that dynamic approaches provide better network balance and utilization.

Traffic engineering has been extensively studied to maximize network resource utilization while minimizing call blocking [1]. As the the demand for high data rate services over wide area networks (WAN) continue to grow [2], and as traffic patterns become subject to more frequent changes, resource utilization and the ability to guarantee quality-of-service become more important. However, accurate, predictive traffic models are difficult to construct [3], implying that the routing mechanism will need to adapt to the difference between the anticipated and the observed loads. Online routing based on network residual capacity plays an important role in such settings, since optimal offline solutions require knowledge of future traffic, rendering long-term optimization nearly impossible. shortest path first (SPF) based routing is fast and is currently the most widely-used online algorithm for optical networks. Many variants of SPF, like CSPF (Constrained SPF), have been proposed to further reduce blocking and network congestion. This paper focuses on the problem of online open routing for connection-oriented optical networks. As part of the major contributions of this paper, we propose a novel online, link-state based routing algorithm called reduced flow routing (RFR), an oracular optimization model, and an efficient network provisioning algorithm. The RFR algorithm uses a fast analysis of each potential route’s impact on future requests to select amongst the available choices. The strategy of RFR leverages information about network topology and residual capacity to reduce blocking by rejecting 20% less connection requests relative to other online routing algorithms with little additional cost. The RFR algorithm can be integrated readily into current and future Generalized Multi-Protocol Label Switching (GMPLS) networks as well as many other relevant networks.

This paper argues for an implicitly parallel programming model for many-core microprocessors, and provides initial technical approaches towards this goal. In an implicitly parallel programming model, programmers maximize algorithm-level parallelism, express their parallel algorithms by asserting high-level properties on top of a traditional sequential programming language, and rely on parallelizing compilers and hardware support to perform parallel execution under the hood. In such a model, compilers and related tools require much more advanced program analysis capabilities and programmer assertions than what are currently available so that a comprehensive understanding of the input program's concurrency can be derived. Such an understanding is then used to drive automatic or interactive parallel code generation tools for a diverse set of parallel hardware organizations. The chip-level architecture and hardware should maintain parallel execution state in such a way that a strictly sequential execution state can always be derived for the purpose of verifying and debugging the program. We argue that implicitly parallel programming models are critical for addressing the software development crises and software scalability challenges for many-core microprocessors.

Survivability becomes increasingly critical in managing high-speed networks as data traffic continues to grow in both size and importance. In addition, the impact of failures is exacerbated by the higher data rates available in optical networks. It is therefore imperative to address network survivability in an efficient manner in order to design and operate reliable networks. Transparent optical networks (TONs) provide several advantages over optically opaque networks for supporting the growing communication demands, but suffer from several drawbacks that reduce the efficacy of most applicable capacity-efficient survivability techniques. In this paper, we present a protection algorithm (for single link and/or node failures) called Streams. Streams protection is identical to 1:1 dedicated path protection in terms of recovery speed, but requires significantly less capacity. We study both online non-dynamic routing as well as (online) dynamic provisioning scenarios to compare Streams with dedicated and shared path protection in terms of capacity, blocking probability, path lengths, and recovery time/data loss, and report the relative tradeoffs between the different protection schemes in detail. Our results show that our simple heuristic for Streams under online provisioning scenarios offer attractive tradeoffs in terms of blocking, recovery speed, data loss and implementation overhead. We also briefly cover simple ILP solutions to address static offline routing problems, and show that the Streams protection scheme is also efficient under offline routing scenarios as well.

Signature analyzers are designed to enable identification of failing test response bits directly from failing signatures, without any special diagnosis mode. This ability is useful for yield learning from the large volume of data available from failing chips during production test. The signature analyzers described also tolerate unknown logic values (X's) and are useful for built-in-self-test and test compression with yield analysis support. Actual defective chip data demonstrates the effectiveness of the presented techniques. Depending on the desired accuracy of failing response bit identification and the number of X's, test response data is reduced by up to two orders of magnitude

This paper presents a hardware-based dynamic optimizer that continuously optimizes an application's instruction stream. In continuous optimization, dataflow optimizations are performed using simple, table-based hardware placed in the rename stage of the processor pipeline. The continuous optimizer reduces dataflow height by performing constant propagation, reassociation, redundant load elimination, store forwarding, and silent store removal. To enhance the impact of the optimizations, the optimizer integrates values generated by the execution units back into the optimization process. Continuous optimization allows instructions with input values known at optimization time to be executed in the optimizer, leaving less work for the out-of-order portion of the pipeline. Continuous optimization can detect branch mispredictions earlier and thus reduce the misprediction penalty. In this paper, we present a detailed description of a hardware optimizer and evaluate it in the context of a contemporary microarchitecture running current workloads. Our analysis of SPECint, SPECfp, and mediabench workloads reveals that a hardware optimizer can directly execute 33% of instructions, resolve 29% of mispredicted branches, and generate addresses for 76% of memory operations. These positive effects combine to provide speed ups in the range 0.99 to 1.27.

Survivability becomes increasingly critical in managing high-speed networks as data traffic continues to grow in both size and importance. In addition, the impact of failures is exacerbated by the higher data rates available in optical networks. It is therefore imperative to address network survivability in an efficient manner in order to design and operate reliable networks. Transparent optical networks (TONs) provide several advantages over optically opaque networks for supporting the growing communication demands, but suffer from several drawbacks that reduce the efficacy of most applicable capacity-efficient survivability techniques. In this paper, we introduce a novel protection algorithm (for single link and node failures) called streams. The streams algorithm is similar to 1:1 dedicated path protection in terms of implementation and operation overhead, and has identical recovery speeds while requiring less capacity. We compare the streams algorithm with dedicated and shared path protection in terms of capacity requirements, path lengths, and recovery time. We also extend the flooding based mesh restoration algorithm (FBMR) in order to provide a fair comparison in online routing scenarios, and report the relative tradeoffs between the different algorithms. Our results show that dynamically routed streams offer attractive tradeoffs in terms of capacity, path length, recovery speed, data loss and implementation complexity.

Stochastic coding is used to design X-tolerant signature analyzers that can detect defective chips even in the presence of unknown logic values (X's). These signature analyzers can be used for built-in-self-test applications and test data compression. Application of this technique to industrial designs shows that thousands of X's can be tolerated while reducing test response data volume by 50 to 2,000 times compared to traditional scan, with practically no impact on test quality.

Modern processors perform dynamic scheduling to achieve better utilization of execution resources. A schedule created at run-time is often better than one created at compile-time as it can dynamically adapt to specific events encountered at execution-time. In this paper, we examine some fundamental impediments to effective static scheduling. More specifically, we examine the question of why schedules generated quasi-dynamically by a low-level runtime optimizer and executed on a statically scheduled machine perform worse than using a dynamically-scheduled approach. We observe that such schedules suffer because of region boundaries and a skewed distribution of parallelism towards the beginning of a region. To overcome these limitations, we investigate a new concept, region slip, in which the schedules of different statically-scheduled regions can be interleaved in the processor issue queue to reduce the region boundary effects that cause empty issue slots.

Inherent within complex instruction set architectures such as /spl times/86 are inefficiencies that do not exist in a simpler ISA. Modern /spl times/86 implementations decode instructions into one or more micro-operations in order to deal with the complexity of the ISA. Since these micro-operations are not visible to the compiler the stream of micro-operations can contain redundancies even in statically optimized /spl times/86 code. Within a processor implementation, however barriers at the ISA level do not apply, and these redundancies can be removed by optimizing the micro-operation stream. In this paper we explore the opportunities to optimize code at the micro-operation granularity. We execute these micro-operation optimizations using the rePLay Framework as a microarchitectural substrate. Using a simple set of seven optimizations, including two that aggressively and speculatively attempt to remove redundant load instructions, we examine the effects of dynamic optimization of micro-operations using a trace-driven simulation environment. Simulation reveals that across a sampling of SPECint 2000 and real /spl times/86 applications, rePLay is able to reduce micro-operation count by 21% and, in particular load micro-operation count by 22%. These reductions correspond to a boost in observed instruction-level parallelism on an 8-wide optimizing rePLay processor by 17% over a non-optimizing configuration.

AQM attempts to provide high network utilization with low loss and delay by regulating queues at bottleneck links. While many AQM algorithms have been proposed, most suffer from instability, require careful configuration of non-intuitive control parameters, or are not practical because of slow response to dynamic traffic changes. In this paper, we propose a new AQM algorithm that combines the more effective elements of recent algorithms with a RED core. Throughput analysis and simulations, we demonstrate improved performance in stability and response time with straightforward selection parameters for both steady load and changes in loads.

No abstract available.

This paper addresses the problem of compacting test responses in the presence of unknowns at the input of the compactor by exploiting the capabilities of well-known error detection and correction codes. The technique, called i-Compact, uses Saluja-Karpovsky Space Compactors, but permits detection and location of errors in the presence of unknown logic (X) values with help from the ATE. The advantages of i-Compact are: 1. Small number of output pins front the compactors for a required error detection capability; 2. Small tester memory for storing expected responses; 3. Flexibility of choosing several different combinations of number of X values and number of bit errors for error detection without altering the hardware compactor; 4. Same hardware capable of identifying the line that produced an error in presence of unknowns; 5. Use of non-proprietary codes found in the literature of 1950s; and 6. Independent of the circuit and the test generator.

In this paper we present an approach to boosting performance and tolerating latency by deferring non-critical instructions into a deferred queue for later processing. As such, instruction deferral allows more critical instructions to be fetched, dispatched, and possibly executed, earlier. We present methods for identifying deferrable instructions using previously investigated notions of instruction slack. In particular we use static slack to determine if an instruction is deferrable. The static slack of an instruction corresponds to the number of cycles an instruction can be delayed without impacting overall execution time when considering all dynamic paths from that instruction. A significant fraction of the dynamic instruction stream has enough static slack to be deferred by 10 or more cycles on an aggressive execution model. Furthermore, the small amount of register-based communication from deferred instructions to non-deferred instructions makes a deferral-based approach to fetch and execution very attractive. We use a trace cache based microarchitecture to overcome some significant implementation challenges associated with instruction deferral. Overall, instruction deferral boosts the performance of a 4-wide processor by approximately 11% and an 8-wide processor by 6% on eight of the SPEC2000 integer benchmarks.

We describe an architecture for an optical local area network (LAN) or metropolitan area network (MAN) access. The architecture allows for bandwidth sharing within a wavelength and is robust to both link and node failures. The architecture can be utilized with an arbitrary, link-redundant mesh network (node-redundancy is necessary only to handle all node failures), and assumes neither the use of a star topology nor the ability to embed such a topology within the physical mesh. Reservation of, bandwidth is performed in a centralized fashion at a (replicated) head end node, simplifying the implementation of complex sharing policies relative to implementation on a distributed set of routers. Unlike a router, however, the head end does not take any action on individual packets and, in particular, does not buffer packets. The architecture thus avoids the difficulties of processing packets in the optical domain while allowing for packetized shared access of wavelengths. We describe the route construction scheme and prove its ability to recover from single link and single node failures, outline a flexible medium access protocol and discuss the implications for implementing specific policies, and propose a simple implementation of the recovery protocol in terms of state machines for per-link devices.

Current means of providing loop-back recovery, which is widely used in SONET, rely on ring topologies, or on overlaying logical ring topologies upon physical meshes. Loop-back is desirable to provide rapid preplanned recovery of link or node failures in a bandwidth-efficient distributed manner. We introduce generalized loop-back, a novel scheme for performing loop-back in optical mesh networks. We present an algorithm to perform recovery for link failure and one to perform generalized loop-back recovery for node failure. We illustrate the operation of both algorithms, prove their validity, and present a network management protocol algorithm, which enables distributed operation for link or node failure. We present three different applications of generalized loop-back. First, we present heuristic algorithms for selecting recovery graphs, which maintain short maximum and average lengths of recovery paths. Second, we present WDM-based loop-back recovery for optical networks where wavelengths are used to back up other wavelengths. We compare, for WDM-based loop-back, the operation of generalized loop-back operation with known ring-based ways of providing loop-back recovery over mesh networks. Finally, we introduce the use of generalized loop-back to provide recovery in a way that allows dynamic choice of routes over preplanned directions.

We study the relationship between failure localization and the properties of link restoration algorithms, employing a quantitative measure of a network's ability to recover from two-link failures. This model allows us to consider issues of failure localization that cannot be addressed through models that assume only single failures. Based on the relationship between algorithmic properties and restoration failures, we construct a failure classification hierarchy that provides insight as to the relative value of advances in algorithm design. Finally, we apply this classification scheme to three networks from the literature and discuss the results in terms of their importance for link restoration algorithms. We find that the topological constraints on restoration paths required by algorithms that embed rings within mesh networks result in significant degradation of failure localization. The preselection of restoration paths (as opposed to selection at the time of failure) also has a negative impact, although it is not as significant as the topological effect. Algorithms that make use of the mesh topology and dynamically route around existing failures come close to an inherent limit imposed by the complexity of additional algorithmic advances.

We evaluate the rePLay microarchitecture as a means for reducing application execution time by facilitating dynamic optimization. The framework contains a programmable optimization engine coupled with a hardware-based recovery mechanism. The optimization engine enables the dynamic optimizer to run concurrently with program execution. The recovery mechanism enables the optimizer to make speculative optimizations without requiring recovery code. We demonstrate that a rePLay configuration performing a small suite of simple optimizations on Alpha code attains an average of 13% reduction in execution cycles on the SPEC2000 integer benchmarks over a rePLay configuration not performing optimizations, and a 21% reduction over an aggressive standard superscalar microarchitecture.

In this paper, we propose a new processor framework that supports dynamic optimization. The rePLay Framework embeds an optimization engine atop a high-performance execution engine. The heart of the rePLay Framework is the concept of a frame. Frames are large, single-entry, single-exit optimization regions spanning many basic blocks in the program's dynamic instruction stream, yet containing only a single flow of control. This atomic property of frames increases the flexibility in applying optimizations. To support frames, rePLay includes a hardware-based recovery mechanism that rolls back the architectural state to the beginning of a frame if, for example, an early exit condition is detected. This mechanism permits the optimizer to make speculative, aggressive optimizations upon frames. In this paper, we investigate some of the underlying phenomenon that support rePLay. Primarily, we evaluate rePLay's region formation strategy. A rePLay configuration with a 256-entry frame cache, using 74 KB frame constructor and frame sequencer, achieves an average frame size of 88 Alpha AXP instructions with 68 percent coverage of the dynamic istream, an average frame completion rate of 92.81 percent, and a frame predictor accuracy of 81.26 percent. These results soundly demonstrate that the frames upon which the optimizations are performed are large and stable. Using the most frequently initiated frames from rePLay executions as samples, we also highlight possible strategies for the rePLay optimization engine. Coupled with the high coverage of frames achieved through the dynamic frame construction, the success of these optimizations demonstrates the significance of the rePLay Framework. We believe that the concept of frames, along with the mechanisms and strategies outlined in this paper, will play an important role in future processor architecture.

Clusters of multiprocessors, or Clumps, promise to be the supercomputers of the future, but obtaining high performance on these architectures requires an understanding of interactions between the multiple levels of interconnection. In this paper, we present the first multi-protocol implementation of a lightweight message layer---a version of Active Messages-II running on a cluster of Sun Enterprise 5000 servers connected with Myrinet. This research brings together several pieces of high-performance interconnection technology: bus backplanes for symmetric multiprocessors, low-latency networks for connections between machines, and simple, user-level primitives for communication. The paper describes the shared memory message-passing protocol and analyzes the multi-protocol implementation with both microbenchmarks and Split-C applications. Three aspects of the communication layer are critical to performance: the overhead of cache-coherence mechanisms, the method of managing concurrent access, and the cost of accessing state with the slower protocol. Through the use of an adaptive polling strategy, the multi-protocol implementation limits performance interactions between the protocols, delivering up to 160 MB/s of bandwidth with 3.6 microsecond end-to-end latency. Applications within an SMP benefit from this fast communication, running up to 75% faster than on a network of uniprocessor workstations. Applications running on the entire Clump are limited by the balance of NIC's to processors in our system, and are typically slower than on the NOW. These results illustrate several potential pitfalls for the Clumps architecture.

: We present and analyze a portable, high-performance algorithm for finding connected components on modern distributed memory multiprocessors. The algorithm is a hybrid of the classic DFS on the subgraph local to each processor and a variant of the Shiloach-Vishkin PRAM algorithm on the global collection of subgraphs. We implement the algorithm in Split-C and measure performance on the the Cray T3D, the Meiko CS-2, and the Thinking Machines CM-5 using a class of graphs derived from cluster dynamics methods in computational physics. On a 256 processor Cray T3D, the implementation outperforms all previous solutions by an order of magnitude. A characterization of graph parameters allows us to select graphs that highlight key performance features. We study the effects of these parameters and machine characteristics on the balance of time between the local and global phases of the algorithm and find that edge density, surface-to-volume ratio, and relative communication cost dominate perform...

No abstract available.

For MPP's to solve new and interesting problems, they must support ihe development of sophisticated algorithms on very large data sets.Successful development depends strongly on the speed of the execute-fix cycle.Sequential machines cannot provide suflciently fast execution of large problems, but many programming systems available on MPP's ;!s date appear, and w+iceis given that copying is by permission of the Asmciation for Compuing Macbkuxy.To copy &envise, or to repubhsb, quires a fee sndor specific prmiskm.