Bloom filters are a probabilistic technique for large-scale set membership tests. They exhibit no false negative test results but are susceptible to false positive results. They are well-suited to both large sets and large numbers of membership tests. We implement the Bloom filters present in an accelerated version of BLAST, a genome biosequence alignment application, on NVIDIA GPUs and develop an analytic performance model that helps potential users of Bloom filters to quantify the inherent tradeoffs between throughput and false positive rates.

Hybrid systems consisting of a multitude of different computing device types are interesting targets for high-performance applications. Chip multiprocessors, FPGAs, DSPs, and GPUs can be readily put together into a hybrid system; however, it is not at all clear that one can effectively deploy applications on such a system. Coordinating multiple languages, especially very different languages like hardware and software languages, is awkward and error prone. Additionally, implementing communication mechanisms between different device types unnecessarily increases development time. This is compounded by the fact that the application developer, to be effective, needs performance data about the application early in the design cycle. We describe an application development environment specifically targeted at hybrid systems, supporting data-flow semantics between application kernels deployed on a variety of device types. A specific feature of the development environment is the availability of performance estimates (via simulation) prior to actual deployment on a physical system.

Profile Hidden Markov models (HMMs) are a powerful approach to describing biologically significant functional units, or motifs, in protein sequences. Entire databases of such models are regularly compared to large collections of proteins to recognize motifs in them. Exponentially increasing rates of genome sequencing have caused both protein and model databases to explode in size, placing an ever-increasing computational burden on users of these systems.Here, we describe an accelerated search system that exploits parallelism in a number of ways. First, the application is functionally decomposed into a pipeline, with distinct compute resources executing each pipeline stage. Second, the first pipeline stage is deployed on a systolic array, which yields significant fine-grained parallelism. Third, for some instantiations of the design, parallel copies of the first pipeline stage are used, further increasing the level of coarse-grained parallelism.A naïve parallelization of the first stage computation has serious repercussions for the sensitivity of the search. We present a pair of remedies to this dilemma and quantify the regions of interest within which each approach is most effective. Analytic performance models are used to assess the overall speedup that can be attained relative to a single-processor software solution. Performance improvements of 1 to 2 orders of magnitude are predicted.

Auto-Pipe is a tool that aids in the design, evaluation and implementation of applications that can be executed on computational pipelines (and other topologies) using a set of heterogeneous devices including multiple processors and FPGAs. It has been developed to meet the needs arising in the domains of communications, computation on large datasets, and real time streaming data applications. This paper introduces the Auto-Pipe design flow and the X design language, and presents sample applications. The applications include the Triple-DES encryption standard, a subset of the signal-processing pipeline for VERITAS, a high-energy gamma-ray astrophysics experiment. These applications are discussed and their description in X is presented. From X, simulations of alternative system designs and stage-to-device assignments are obtained and analyzed. The complete system permits production of executable code and bit maps that may be downloaded onto real devices. Future work required to complete the Auto-Pipe design tool is discussed.

To provide a variety of new and advanced communications services, computer networks are required to perform increasingly complex packet processing. This processing typically takes place on network routers and their associated components. An increasingly central component in router design is a chip-multiprocessor (CMP) referred to as "network processor" or NP. In addition to multiple processors, NPs have multiple forms of on-chip memory, various network and off-chip memory interfaces, and other specialized logic components such as CAMs (content addressable memories). The design space for NPs (e.g., number of processors, caches, cache sizes, etc.) is large due to the diverse workload, application requirements, and system characteristics. System design constraints relate to the maximum chip area and the power consumption that are permissible while achieving defined line rates and executing required packet functions. In this paper, an analytic performance model that captures the processing performance, chip area, and power consumption for a prototypical NP is developed and used to provide quantitative insights into system design trade offs. The model, parameterized with a networking application benchmark, provides the basis for the design of a scalable, high-performance network processor and presents insights into how best to configure the numerous design elements associated with NPs

This paper presents a general system architecture tailored to perform searching, filtering, compression, encryption, and other operations on unstructured data streaming from a disk system. The system achieves high performance on such applications by providing for parallelism, hardware-application specialization and reconfiguration, and hardware placement near the disk systems. A limited prototype of a single compute node has been implemented and is described. The prototype is tailored to applications involving complex searching and its performance is compared to a pure software implementation having the same search capabilities. Performance is considered in terms of data set size, query string hit rate and query complexity. Performance results as a function of these parameters are presented and the results indicate that, for data set sizes above 1.4 MB, the prototype compute node is between one and two orders of magnitude faster than a pure software implementation. At high data set sizes, on an individual node, speedups of about 200 and a sustained throughput of 300 MB/sec have been achieved.

This paper considers a class of embedded signal processing applications. To achieve real-time performance these applications must be executed on a parallel processor. The paper focuses on the multiring optical interconnection network used in the system and specifically on the performance gains associated with utilizing the bandwidth reconfiguration capabilities associated with the network. The network is capable of being reconfigured to provide designated bandwidths to different source-destination connections both across rings and within a ring. The applications each consist of a sequence of alternating communication and computation phases. The sequence continues until execution of the application is complete. The effect of reconfiguration on application performance is explored using simulation techniques. The results indicate that substantial performance gains (speedups of 2 or more) can be achieved for this application class.

The implementation of computational systems to perform challenging operations often involves balancing the performance specification, system throughput, and available system resources. For problems of automatic target recognition (ATR), these three quantities of interest are the probability of classification error, the rate at which regions of interest are processed, and the capabilities of the underlying hardware (which is a function of the available computational resources and available power). An understanding of the inter-relationships between these factors can be an aid in making informed choices while exploring competing design possibilities. Combining characterizations of ATR performance, which yield probability of classification error as a function of target model complexity, with analytical models of computational performance, which yield throughput as a function of target model complexity and available resources, we can form a set of parametric curves which relate the quality of the results to the resources consumed.

The Gemini interconnect is a dual technology (optical and electrical) interconnection network designed for use in tightly-coupled multicomputer systems. It consists of a circuit-switched optical data path in parallel with a packet-switched electrical control/data path. The optical path is used for transmission of long data messages and the electrical path is used for switch control and transmission of short data messages. The paper describes the architecture of the interconnection network and related communications protocols. Fairness issues associated with network operation are addressed and a discrete-event simulation model of the entire system is described. Network performance characteristics derived from the simulation model are presented. The results show significant performance benefits when using virtual output queuing and quantify the tradeoffs between throughput and fairness in the system.

Demands for flexible processing have moved generalpurpose processing into the data path of networks. Processor schedulers have a great impact on the performance of these real-time systems. We present measurements that show that the workload of a network processor is highly regular and predictable. Processing time predictions, based on these measurements, can be used in scheduling together with information about locality in the instruction stream to significantly improve throughput performance. We propose two scheduling schemes, Locality-Aware and Locality-Aware Predictive, that try to avoid cold caches when scheduling packets for processors. Simulations of the schedulers using packet processing times obtained from an operational network processor show the tradeoffs between the algorithms and their performance improvements over First-Come-FirstServe scheduling.

The paper presents a benchmark, CommBench, for use in evaluating and designing telecommunications network processors. The benchmark applications focus on small, computationally intense program kernels typical of the network processor environment. The benchmark is composed of eight programs, four of them oriented towards packet header processing and four oriented towards data stream processing. The benchmark is defined and characteristics such as instruction frequencies, computational complexity, and cache performance are presented. These measured characteristics are compared to the standard SPEC benchmark. Three examples are presented indicating how CommBench can aid in the design of a single chip network multiprocessor.

Existing fair scheduling schemes have focused primarily on scheduling multiple flows to a single output. The limited work that has focused on scheduling multiple flows to multiple outputs has assumed a non-blocking, slotted-time, cell-based network with a centralized controller. This paper presents a fair scheduler suitable for use in bufferless circuit-switched blocking networks operating with distributed, asynchronous controllers and variable length messages. We begin by describing the potential for starvation in the Gemini interconnect network, an optical, circuit-switched network. A proposed distributed fair scheduler is presented and shown to solve this problem. The tradeoffs and limitations of performing many-to-many fair scheduling in general, and that of our fair scheduler in particular, are discussed.

In this paper, we present methods for improving the performance of self-timed computation blocks. The Hybrid Completion method permits the design of a spectrum of completion circuits ranging from those based on pure bounded delays to those based on full complementary circuit development. This is achieved by using a subset of the outputs of the computation block to generate the overall completion signal. Thus, the extra circuitry for the completion signals of the other outputs is eliminated. The computation block's delay might also be reduced since fewer signals are required to generate the overall completion signal. The approach seeks to incorporate the area efficiency of the bounded delay approach and the operand based delay sensitivity of the full complementary approach.

Communication latencies and delays are a major source of performance degradation in parallel computing systems. It is important to "mask" these communication delays by overlapping them with useful computation in order to obtain good parallel performance. This article proposes speculative computation as a technique to mask communication latencies in synchronous iterative algorithms. Processors speculate the contents of messages that are not yet received and perform computation based on the speculated values. When the messages are received, they are compared with the speculated values and, if the error is unacceptable, the resulting computation is corrected or recomputed. If the error is small, the speculated value is accepted and the processor has masked the communication delay. The technique, applied to N-body simulations yielded a performance improvement of up to 34%.

This paper examines the performance of synchronous checkpointing in a distributed computing environment with and without load redistribution. Performance models are developed, and optimum checkpoint intervals are determined. The analysis extends earlier work by allowing for multiple nodes, state dependent checkpoint intervals, and a performance metric which is coupled with failure-free performance and the speedup functions associated with implementation of parallel algorithms. Expressions for the optimum checkpoint intervals for synchronous checkpointing with and without load redistribution are derived and the results are then used to determine when load redistribution is advantageous.>

Deeply pipelined processors increase the cost of executing conditional branches. Several branch architectures based on both hardware and software techniques have been proposed to reduce this cost. A popular branch mechanism based on software techniques is static branch prediction with delay slot annulling. This mechanism reduces the cost of conditional branches by making delay slots visible in the architecture. Architectural visibility allows the software to exploit delay slots by executing instructions speculatively. The visibility of the delay slots, however, also results in an increase in code size; compilers must find appropriate instructions which can be scheduled into the delay slots. If no "useful" instructions can be found, then nops must be inserted in the delay slot. The authors propose a novel branch architecture called prophetic branches which allows compilers to exploit branch delays, yet could result in only a minimal increase in code size over non-pipelined code. They show that this branch mechanism can be implemented in deeply pipelined processors with only a minor change in the control logic.>

A parallel simulated annealing algorithm that is problem-independent, maintains the serial decision sequence, and obtains speedup which can exceed log/sub 2/P on P processors is discussed. The algorithm achieves parallelism by using the concurrency technique of speculative computation. Implementation of the parallel algorithm on a hypercube multiprocessor and application to a task assignment problem are described. The simulated annealing solutions are shown to be, on average, 28% better than the solutions produced by a random task assignment algorithm and 2% better than the solutions produced by a heuristic.>

Simulated annealing for obtaining approximate solutions to combinatorial optimization problems is addressed. The serial algorithm, however, can require extensive computation time. Most parallel algorithms for simulated annealing are problem-specific and/or violate the serial decision sequence, thereby allowing errors not present in the serial algorithm. Maintaining the serial sequence is necessary to prove that the algorithm converges to a global optimum solution when allowed to reach equilibrium at each temperature. A parallel algorithm which is both problem-independent and maintains the serial decision sequence is presented. The parallel algorithm uses the concurrency techniques of speculative computation to achieve speedup which can exceed log/sub 2/P, on P processors. For three problems investigated, the average speedup on eight processors was 2.6.>

A performance model for a hierarchical discrete-event-simulation algorithm running on a hypercube architecture is presented. A static allocation of system components to hypercube processors and a global clock algorithm with an event-based time increment are assumed. The model is applied to a digital systems simulation. The effects of different architectures, algorithm parameter values, and partitioning strategies on speedup are evaluated.>

The authors present a method for parallelizing the simulated annealing algorithm by mapping the algorithm onto a dynamically structured tree of processors. The resulting parallel simulated annealing algorithm is discussed and its performance evaluated using simulation techniques. An important property of the parallel algorithm is that it maintains the same move decision sequence as the serial simulated annealing algorithm, thus avoiding problems associated with move conflicts and erroneous move acceptance/rejection decisions which have been associated with other parallel simulated annealing algorithm proposals. The parallel algorithm presented achieves speedups between log/sub 2/N and (N+log/sub 2/N)/2 where N is the number of processors in the parallel processor. Experimental results are presented on three versions of the basic method: the static, dynamic balanced, and dynamic unbalanced parallel-simulated-annealing algorithms.>

Due to the high cost associated with generating effective input vectors to test MOS circuits, finding ways to reduce this test vector generation cost is of considerable interest. Empirical results show that fault coverage obtained from MOS transistor-level fault simulation using randomly generated test inputs can be approximated by the fault coverage obtained using the test vectors generated from classical stuck-at-zero and stuck-at-one fault simulation on logic-gate-level circuits. Applying this result, an approach is presented to reduce the cost of test vector generation for MOS circuits.>

The high costs associated with logic simulation of large VLSI circuits has led to the need for new computer architectures tailored to the simulation task. Such architectures have the potential for significant speed-ups over software-based logic simulators executing on standard sequential computers. This paper presents a model of one class of multiprocessor simulation architectures and compares the performance of some of these machines using data obtained from simulations of VLSI circuits. In addition, we discuss the implications of our results on machine design and examine the sensitivity of the model to variations in circuit characteristics.

The high costs associated with logic simulation of large VLSI based systems have led to the need for new computer architectures tailored to the simulation task. Such architecture have the potential for significant speedups over standard software based logic simulators. Several commercial simulation engines have been produced to satisfy need in this area. To properly explore the space of alternative simulation architectures, data is required on the simulation process itself. This paper presents a framework for such data gathering activity by first examining possible sources of speedup in the logic simulation task, examining the sort of data needed in the design of simulation engines, and then presenting such data. The data contained in the paper includes information on the subtask times found in standard discrete event simulation algorithms, event intensities, queue length distributions and simultaneous event distributions.

Design of high-performance hardware and software-based gate-switch-level logic simulators requires knowledge about the logic simulation process itself. Unfortunately, little data is publicly available concerning key aspects of this process. An example of this is the lack of published empirical measurements relating to the time distribution of events generated by such simulators. This paper presents a gate-switch-level logic simulator lsim which is oriented towards the collection of data about the simulation process. The basic components of lsim are reviewed, and its relevant data gathering facilities are discussed. An example is presented which illustrates the use of lsim in gathering data on event distributions and on communications requirements under alternative logic circuit partitionings.

A central issue in the design of multiprocessor systems is the interconnection network which provides communication paths between the processors. For large systems, high bandwidth interconnection networks will require numerous "network chips" with each chip implementing some subnetwork of the original larger network. Modularity and growth are important properties for such networks since multiprocessor systems may vary in size. This paper is concerned with the question of timing control of such networks. Two approaches, asynchronous and clocked, are used in the design of a basic network switching module. The modules and the approaches are then modeled and equations for network time delay are developed. These equations form the basis for a comparison between the two approaches. The importance of clock distribution strategies and clock skew is quantified, and a network clock distribution scheme which guarantees equal length clock paths is presented.

A central issue in the design of multiprocessor systems is the interconnection network which provides communications paths between the processors. For large systems, high bandwidth interconnection networks will require numerous 'network chips' with each chip implementing some subnetwork of the original larger network. Modularity and growth are important properties for such networks since multiprocessor systems may vary in size. This paper is concerned with the question of timing control of such networks. Two approaches, asynchronous and clocked, are used in the design of a basic network switching module. The modules and the approaches are then modelled and equations for network time delay are developed. These equations form the basis for a comparison between the two approaches. The importance of clock distribution strategies and clock skew is quantified, and a network clock distribution scheme which guarantees equal length clock paths is presented.

Multiple processor interconnection networks can be characterized as having N' inputs and N' outputs, each being B' bits wide. A major implementation constraint of large networks in the VLSI environment is the number of pins available on a chip, Np. Construction of large networks requires partitioning of the N' * N' * B' network into a collection of N * N switch modules with each input and output port being B (B ≤ B') bits wide. If each module corresponds to a single chip, then a large network can be implemented by interconnecting the chips in a particular manner. This correspondence presents a methodology for selecting the optimum values of N and B given values of N', B', Np, and the number of control lines per port. Models for both banyan and crossbar networks are developed and arrangements yielding minimum: 1) number of chips, 2) average delay through the network, and 3) product of number of chips and delay, are presented.

The performance characteristics of banyan and crossbar communications networks are compared in a VLSI environment, where it is assumed that the entire network resides on a single VLSI chip and operates in a circuit switched mode. A high-level model of the space (area) and time (delay) requirements for these networks is developed and relative performance comparisons are made based on a space-time product measure. The results differ significantly from those obtained with more traditional analyses which are usually based on switch aggregate comparisons and SSI-based delay calculations. The analysis presented shows that the area required by both networks grows as 0(N2). Time delay grows as 0(N) for the crossbar, and approximately 0[ Na(log2N)2] for the banyan where 0 < a < 1. This contrasts with traditional results which yield 0(N log N) and 0(log N) switch and delay growth for banyan networks.

This paper presents a straightforward approach to determining how best to utilize an MIMD multiprocessor in the solution of one-dimensional optimization problems involving continuous unimodal functions and nongradient search techniques. A methodology is presented which allows one to consider a variety of speedup functions which may occur in parallel function and systems evaluation. It is shown how the best of two parallel optimization strategies can be determined for a given accuracy, number of processors, and speedup function.

The design of a modular crossbar network that can be used to support a multiprocessor is reviewed in this paper. The network is viewed at a functional level and the objectives, motivations and resultant design decisions are discussed. Two of these decisions relating to the nature and depth of pipelining in the network are examined in detail. The network designed is expandable in an easy fashion, flexible and suitable for large-scale integration.

This paper presents a performance comparison of three parallel algorithms for the solution of sets of coupled first-order differential equations. A general format for comparison of the algorithms is given, and performance equations for the two processor cases are developed. The equations take into account both the computational and intercommunications requirements of the processors. These equations are applied to a benchmark of six problems and a simple, single bus multiprocessor architecture. The more than two processor case is considered for one of the parallel algorithms.

Performance of a paged virtual memory computer system operating under working set (WS) and page fault frequency (PFF) paging algorithms is analyzed analytically. Performance sensitivity to program reference behavior and paging algorithm parameter is studied for the two paging algorithms. The results indicate that when performance with the two algorithms is compared, the WS algorithm is generally less sensitive to changes in program behavior. Results are also provided relating to performance sensitivity to algorithm parameter selection.

Abstract A first order Markov model of program behaviour is developed from FORTRAN program instruction data. The program model is evaluated by using it to generate page references for input into a simple virtual memory operating system (VMOS) simulation model. The actual trace data are also used to drive the VMOS model. In both cases the fault probability is obtained for different replacement rules, memory sizes and page sizes. A comparison of fault probabilities is used to determine the effectiveness of the Markov program model.

An empirical heuristic learning identification algorithm of Ivakhnenko was modified and used to model an environmental system producing high nitrate levels in agricultural drain water in the Corn Belt. The method amounts to fitting a polynomial to a multi-input single-output response surface. The modifications result in a reduced number of terms in final model equations, a decrease in computational difficulties, and other improvements in the algorithm. This method appears to be advantageous with systems characterized by complexity with many variables and parameters, ill-defined mathematical structures, and limited data. In other words, this algorithm is useful for empirically generating hypotheses about systems of which relatively little is known.

The question of replacing a single-density, two-channel, two-controller disk system with a cheaper, plug-compatible, dual-density, single-channel system having the same capacity is considered. An analytical model is explored to examine the effect of such a replacement on average response time, that is, the time between issuing an I/O request and completion of the request. Queueing theory is used to obtain curves of response time versus arrival rate, and the results are compared with corresponding curves obtained by a simulation model.

The discrete Monte Carlo method for the solution of partial differential equations has been studied theoretically and experimentally. A special purpose digital computer, the PDE machine, was designed and constructed from macromodules, and Monte Carlo solutions for illustrative problems were obtained. Error analysis has been made and experimental outcomes were compared with theoretical results. Using Monte Carlo methods the PDE machine has been proved to be very efficient from the viewpoint of accuracy and speed in comparison to the general purpose digital computer. Speeds of one solution every 2 seconds were obtained for Poisson's equations with a typical accuracy of better than 2 percent of the range of solutions.