This talk will describe how AI/Machine Learning is being applied to the field of Engineering Simulation and Electronic Design Automation. First, we will describe how AI/ML can be used to speed up engineering simulation by developing surrogate models by training neural networks using actual multi-physics simulations over various CAD models, and different boundary conditions. This requires the customers to train the AI models using an AI platform. Second, we will discuss how to develop foundational models for simulation by training AI models over a wide range of CAD models and boundary conditions. This approach does not require the customer to train any AI models, but instead they can use pretrained models on any given CAD geometry. Third, we will discuss how AI/ML models are used to make simulation tools easier to use by automatically setting the parameters of the simulation tools in order to get the best performance and accuracy. Fourth, we will discuss how generative models can be used to explore new designs and optimize product designs. Next, we will explore how AI/ML methods are used in electronic design automation tools such as placement, routing, synthesis and verification using reinforcement learning. These techniques have been used for design space optimization, analog space optimization, verification space optimization, and test space optimization. Finally, we will conclude the talk by showing how Agentic AI techniques can be used in engineering simulation and EDA to automate various tasks and workflows using the concept of ''Agent Engineers''.

We introduce HOT3D, a publicly available dataset for egocentric hand and object tracking in 3D. The dataset offers over 833 minutes (3.7M+ images) of recordings that feature 19 subjects interacting with 33 diverse rigid objects. In addition to simple pickup, observe, and put-down actions, the subjects perform actions typical for a kitchen, office, and living room environment. The recordings include multiple synchronized data streams containing egocentric multi-view RGB/monochrome images, eye gaze signal, scene point clouds, and 3D poses of cameras, hands, and objects. The dataset is recorded with two headsets from Meta: Project Aria, which is a research prototype of AI glasses, and Quest 3, a virtual-reality headset that has shipped millions of units. Ground-truth poses were obtained by a motion-capture system using small optical markers attached to hands and objects. Hand annotations are provided in the UmeTrack and MANO formats, and objects are represented by 3D meshes with PBR materials obtained by an in-house scanner. In our experiments, we demonstrate the effectiveness of multi-view egocentric data for three popular tasks: 3D hand tracking, model-based 6DoF object pose estimation, and 3D lifting of unknown in-hand objects. The evaluated multi-view methods, whose benchmarking is uniquely enabled by HOT3D, significantly outperform their single-view counterparts.

A world consisting of billions of service-oriented client devices and thousands of data centers can deliver a diverse range of services, from social networking to management of our natural resources. However, these services must scale in order to meet the fundamental needs of society. To enable such scaling, the total cost of ownership of the data centers that host the services and comprise the vast majority of service delivery costs will need to be reduced. As energy drives the total cost of ownership of data centers, there is a need for a new paradigm in design and management of data centers that minimizes energy used across their lifetimes, from “cradle to cradle”. This tutorial article presents a blueprint for a “net-zero data center”: one that offsets any electricity used from the grid via adequate on-site power generation that gets fed back to the grid at a later time. We discuss how such a data center addresses the total cost of ownership, illustrating that contrary to the oft-held view of sustainability as “paying more to be green”, sustainable data centers—built on a framework that focuses on integrating supply and demand management from end-to-end—can concurrently lead to lowest cost and lowest environmental impact.

A large body of data-flow analyses exists for analyzing and optimizing sequential code. Unfortunately, much of it cannot be directly applied on parallel code, for reasons of correctness. This article presents a technique to automatically, aggressively, yet safely apply sequentially-sound data-flow transformations, without change , on shared-memory programs. The technique is founded on the notion of program references being “siloed” on certain control-flow paths. Intuitively, siloed references are free of interference from other threads within the confines of such paths. Data-flow transformations can, in general, be unblocked on siloed references. The solution has been implemented in a widely used compiler. Results on benchmarks from SPLASH-2 show that performance improvements of up to 41% are possible, with an average improvement of 6% across all the tested programs over all thread counts.

A common approach to activity recognition has been the use of histogram of codewords computed from Spatio Temporal Interest Points (STIPs). Recent methods have focused on leveraging the spatio-temporal neighborhood structure of the features, but they are generally restricted to aggregate statistics over the entire video volume, and ignore local pairwise relationships. Our goal is to capture these relations in terms of pairwise cooccurrence statistics of codewords. We show a reduction of such cooccurrence relations to the edges connecting the latent variables of a Conditional Random Field (CRF) classifier. As a consequence, we also learn the codeword dictionary as a part of the maximum likelihood learning process, with each interest point assigned a probability distribution over the codewords. We show results on two widely used activity recognition datasets.

Programming with atomic sections is a promising alternative to locks since it raises the abstraction and removes deadlocks at the programmer level. However, implementations of atomic sections using software transactional memory (STM) support have significant bookkeeping overheads. Additionally, because of the speculative nature of transactions, aborts can be frequent greatly lowering application performance. Thus regardless of the STM implementation, tools need to be available to programmers that provide insights into the runtime characteristics of an application as well as provide means to improve performance. This paper attempts to identify the source of an abort at the granularity of a transactional memory reference. The resulting abort patterns are captured in the form of a runtime abort graph (RAG). We show how to build this graph efficiently using compiler instrumentation. We then describe a technique that works on the RAG and automatically recommends STM policy changes to improve performance. Detailed experimental results are presented showing the tradeoffs in building the RAG and its use in reducing aborts and improving performance.

A large body of data-flow analyses exists for analyzing and optimizing sequential code. Unfortunately, much of it cannot be directly applied on parallel code, for reasons of correctness. This paper presents a technique to automatically, aggressively, yet safely apply sequentially-sound data-flow transformations, without change, on shared-memory programs. The technique is founded on the notion of program references being "siloed" on certain control-flow paths. Intuitively, siloed references are free of interference from other threads within the confines of such paths. Data-flow transformations can, in general, be unblocked on siloed references.

A novel representation of vehicle trajectories is proposed for applications in trajectory analysis and activity detection. Specifically, a piecewise arc fitting based smoothing algorithm is proposed for denoising the trajectories. A dynamic program is used to find the optimal arc fit to a given trajectory. We motivate the usage of dynamic primitives to parametrize common vehicular activities, and propose a dynamics based trajectory segmentation algorithm. Each primitive is modeled using a second order Auto-Regressive model, and form useful descriptors for a given vehicular trajectory. We evaluate both our trajectory smoothing and dynamic trajectory segmentation algorithm on a real UAV video dataset, and show performance improvements which clearly motivate its wide applicability in a general trajectory analysis system.

We describe a novel approach for automatically generating streaming architectures from software programs. While existing systems require user-defined stream models, our method automatically identifies producer-consumer streaming relationships and translates them into streaming architectures. Data streams between producer-consumer kernels are represented using a combination of stream descriptors and CFGs, which are categorized into four stream types. A bridge module is generated based on the stream type in the streaming architecture to facilitate data streaming between each producer-consumer pair. Several optimizations are also developed to improve throughput and parallelism. We demonstrate our results on a FPGA based platform. The automatically generated streaming architectures show 1.5-3x speedups over the non-streaming designs by employing spatial and temporal data independence to increase parallelism.

Iterative retiming and resynthesis is a powerful way to optimize sequential circuits but its massive adoption has been hampered by the hardness of verification. This paper tackles the problem of retiming and resynthesis equivalence checking on a pair of circuits. For this purpose we define the Complete-k-Distinguishability (C-k-D) property for any natural number k based on C-1-D. We show how the equivalence checking problem can be simplified if the circuits satisfy this property and prove that the method is complete for any number of retiming and resynthesis steps. We also provide a way to enforce C-k-D on the circuits without restricting the optimization power of retiming and resynthesis or increasing their complexity. Experimental results demonstrate that enforcing C-k-D property can speed up the verification process.

The environmental impact of data centers is significant and is growing rapidly. Servers alone in the US consumed 1.2% of the nation's energy in 2005, according to the EPA. In the following year, the EPA found that the cost of energy rose by 10%. However, there are many opportunities for greater efficiency through integrated design and management of data center components. To that end, we propose a sustainable data center that replaces conventional resource delivery models with a framework centered around the supply and demand side management of all data center resources including IT, power and cooling. We have identified five elements for achieving this vision: data center scale lifecycle design, flexible and configurable building blocks, pervasive cross-layer sensing, knowledge discovery and visualization, and autonomous control. We describe these principles and provide selected results that quantify the potential for savings.

This paper describes an FPGA based implementation of a real time compression algorithm used in transactions between financial institutions such as exchanges and trading houses. FIX is a protocol that has gained widespread popularity for exchanging financial information such as stock prices and purchases over the Internet. If a financial trader can speed up the processing of these protocols, he can make significant financial profits by buying or selling stocks when there is a lot of variability in the share prices. Our methodology tries to recognize and exploit streaming characteristics of the software design in order to implement a pipelined parallel processing system in reconfigurable hardware. It introduces the concept of caches to keep stream pipelines filled more often. The system implemented on a Xilinx Virtex5 LX110T FPGA shows a 17x speedup in throughput over a software implementation running on a dual core Intel Pentium workstation. These techniques are being developed as part of commercial compiler project to automatically translate software binaries to streaming RTL VHDL systems.

An intelligent IT Infrastructure will deliver extremely high performance, adaptability and security to users in the future. Building on the advancements in utility computing, smart data centers, automation, virtualization and intelligent networks, Hewlett Packard Labs is positioning itself to redefine datacenters, networks, software and devices. This talk will provide an overview of research being performed at HP Labs on four areas that will enable an Intelligent Infrastructure: Computing, storage, networking and nanotechnology. 1) We're helping transition computing to exascale computing, in which every processor chip has multiple CPU cores, and a new generation of software puts these parallel processes to good use; 2) We're building a cloud-scale, intelligent storage system that is self-managed and enterprise-grade; 3) A programmable wired and wireless network platform will make the introduction of new features quick, easy and cost-effective; 4) And breakthroughs in nanotechnology are going to revolutionize the way data is collected, stored and transmitted, using technologies such as the memristor and photonic interconnects.

With the proliferation of reconfigurable systems and flexible memory architectures, there has been intense interest in stream systems. While the existing stream systems require the programs to be written using special models, this paper demonstrates an approach to automatically generate stream programs from existing applications written for non-stream scalar processors. As a part of this approach, we provide a new comparison methodology and an algorithm to automatically generate stream descriptions. A second algorithm identifies processing kernels that can be pipelined. We demonstrate our results on an FPGA based platform.

Many new real-time system require high-speed compression and decompression solutions that provide low latency links between systems over a network interface. We describe a methodology for implementing an optimized streaming ZLIB decoder system on a Xilinx Virtex-5 FPGA board, which exploits the fine-grain parallelism in the software architecture to improve the performance. We describe a ZLIB decoder system in hardware and concrete examples of how to transform the sequential software algorithm into a highly optimized hardware implementation in RTL VHDL. Experimental results show 50times speedup in terms of cycles and 2.83times speedup in terms of time in the FPGA over the software. The ZLIB decoder was shown to operate at a rate of 1 GBit/s.

In this paper we present a System-Level technique for reducing energy consumption. The technique is applicable to pipelined applications represented as chain-structured graphs and targets the energy overhead of switching between active and sleep mode. The overhead is reduced by increasing the number of consecutive executions of the pipeline stages. The technique has no impact on the average throughput. We derive upper bounds on the number of consecutive executions and present a dynamic-programming algorithm that finds the optimal solution using these bounds. For specific cases we derive a quality metric that can be used to trade quality of the result for running-time.

Self-stabilizing systems are systems that automatically recover from any transient fault. Proving the correctness of a parameterized self-stabilizing system, i.e., a system composed of an arbitrary number of processes, is a challenging task. For the verification of parameterized systems the method of control abstraction has been developed. However, control abstraction can only be applied to systems in which each process has a fixed number of observable variables. In this article, we propose a technique to abstract a parameterized self-stabilizing system, whose processes have a parameterized number of observable variables, to a system with fixed number of observable variables. This enables the use of control abstraction for verification. The proposed technique targets low-atomicity, shared-memory, asynchronous systems. We establish the completeness of the method under reasonable conditions and demonstrate its effectiveness by applying it on a number of self-stabilizing distributed systems.

In this paper we present a new algorithm for retiming synchronous dataflow (SDF) graphs. The retiming aims at minimizing the cycle length of an SDF. The algorithm is provably optimal and its execution time is improved compared to previous approaches.

Abstract A whole‐program MATLAB to C translation system is presented. The paper outlines the motivation for the problem, discusses the system's architecture, its features and limitations. The translator's operation is explained using an example input program. Details are given on how the system implements and specializes some of the language's built‐in primitives. Finally, the paper reports measurements evaluating the execution time and memory usage of the translated sources, and the compilation time required for the translations. Copyright © 2006 John Wiley & Sons, Ltd.

The modern era of embedded system design is geared toward the design of low-power systems. One way to reduce power in an application-specified integrated circuit (ASIC) implementation is to reduce the bit-width precision of its computation units. This paper describes algorithms to optimize the bit widths of fixed-point variables for low power in a SystemC-based ASIC design environment. We propose an optimal bit-width allocation algorithm for two variables and a greedy heuristic that works for any number of variables. The algorithms are used in the automation of converting floating-point SystemC programs into ASIC synthesizable SystemC programs. Expected inputs are profiled to estimate errors in the finite precision conversions. Experimental results for the tradeoffs between quantization error, power consumption, and hardware resources used are reported on a set of four SystemC benchmarks that are mapped onto a 0.18-mum ASIC cell library from Artisan Components. We demonstrate that it is possible to reduce the power consumption by 50% on the average by allowing roundoff errors to increase from 0.5% to 1%

As new applications in embedded communications and control systems push the computational limits of digital signal processing (DSP) functions, there will be an increasing need for software applications to be migrated to hardware in the form of a hardware-software codesign system. In many cases, access to the high-level source code may not be available. It is thus desirable to have a technology to translate the software binaries intended for processors to hardware implementations. This paper provides details on the retargetable FREEDOM compiler. The compiler automatically translates DSP software binaries to register-transfer level (RTL) VHDL and Verilog for implementation on field-programmable gate arrays (FPGAs) as standalone or system-on-chip implementations. We describe the underlying optimizations and some novel algorithms for alias analysis, data dependency analysis, memory optimizations, procedure call recovery, and back-end code scheduling. Experimental results on resource usage and performance are shown for several program binaries intended for the Texas Instruments C 6211 DSP (VLIW) and the ARM 922 T reduced instruction set computer (RISC) processors. Implementation results for four kernels from the Simulink demo library and others from commonly used DSP applications, such as MPEG-4, Viterbi, and JPEG are also discussed. The compiler generated RTL code is mapped to Xilinx Virtex II and Altera Stratix FPGAs. We record overall performance gains of 1.5-26.9 for the hardware implementations of the kernels. Comparisons with the power aware compiler techniques (PACT) high-level synthesis compiler are used to show that software binaries can be used as intermediate representations from any high-level language and generate efficient hardware implementations.

The modern era of embedded system design is geared towards design of low-power systems. One way to reduce power in an ASIC implementation is to reduce the bit-width precision of its computation units. This paper describes algorithms to optimize the bit-widths of fixed point variables for low power in a SystemC design environment. We propose an algorithm for optimal bit width precision for two variables and a greedy heuristic which works for any number of variables. The algorithms are used in the automation of converting floating point SystemC programs into ASIC synthesizable SystemC programs. Expected inputs are profiled to estimate errors in the finite precision conversions. Experimental results on the trade-offs between quantization error, power consumption and hardware resources used are reported on a set of four SystemC benchmarks that are mapped onto 0.18 micron ASIC cell library from Artisan Components. We demonstrate that it is possible to reduce the power consumption by 50% on average by allowing round-off errors to increase from 0.5% to 1%. 1

The problem of inferring array shapes ahead of time in languages that exhibit both implicit and dynamic typing is a critical one because the ramifications of its solution are the better organization of array storage through compaction and reuse, and the generation of high-performance code through specialization by shape. This article addresses the problem in a prototypical implicitly and dynamically typed array language called MATLAB. The approach involves modeling the language's shape semantics using an algebraic system, and applying term rewriting techniques to evaluate expressions under this algebra. Unlike prior efforts at array shape determination, this enables the deduction of valuable shape information even when array extents are compile-time unknowns. Furthermore, unlike some previous methods, our approach doesn't impose monotonicity requirements on an operator's shape semantics. The work also describes an inference methodology and reports measurements from a type inference engine called MAGICA. In a benchmark suite of 17 programs, the shape inference subsystem in MAGICA detected the equivalence of over 61% of the symbolic shapes in six programs, and over 57% and 37% of the symbolic shapes in two others. In the remaining nine programs, all array shapes were inferred to be compile-time constants.

This paper describes a method for automatically extracting function bodies from linked software binaries. It utilizes procedure-calling conventions along with limited control and data flow information. It has been tested with the TI C6000 DSP processor platform. Results are reported on eight benchmarks for which our algorithm successfully identifies all functions. It identifies 198% more functions than by the use procedure calling conventions alone.

In this paper a new framework for formal verification is presented. The new framework called EVRM (Efficient VeRification based on Mathematica [1]) can be used for the property verification of a Register Transfer Level implementation using a System Level description as the golden model. EVRM is based on word level techniques and uses theMathematica tool for the satisfiability procedure. Results show that it can be orders of magnitude faster than CBMC [2] in proving property correctness or providing a counterexample for computation-intensive applications. For certain applications CBMC requires more than 5 hours to provide an answer, while EVRM provides an answer in less than 10 minutes.

In this paper we address the problem of module selection during high-level synthesis. We present a heuristic algorithm for leakage power optimization based on the maximum weight independent set problem. A dual threshold voltage (Vth) technique is used to reduce leakage energy consumption in a data flow graph. Experiments are performed on a data-path dominated test suite of six benchmarks. Our approach achieves an average of 70.9% leakage power reduction, which is very close to the optimal results from an Integer Linear Programming approach.

Most practical FPGA designs of digital signal processing (DSP) applications are limited to fixed-point arithmetic owing to the cost and complexity of floating-point hardware. While mapping DSP applications onto FPGAs, a DSP algorithm designer must determine the dynamic range and desired precision of input, intermediate, and output signals in a design implementation. The first step in a MATLAB-based hardware design flow is the conversion of the floating-point MATLAB code into a fixed-point version using "quantizers" from the filter design and analysis (FDA) toolbox for MATLAB. This paper describes an approach to automate the conversion of floating-point MATLAB programs into fixed-point MATLAB programs, for mapping to FPGAs by profiling the expected inputs to estimate errors. Our algorithm attempts to minimize the hardware resources while constraining the quantization error within a specified limit. Experimental results on five MATLAB benchmarks are reported for Xilinx Virtex II FPGAs.

The introduction of advanced FPGA architectures, with built-in DSP support, has given DSP designers a new hardware alternative. By exploiting its inherent parallelism, it is expected that FPGAs can outperform DSP processors. This paper describes the process and considerations for automatically translating binaries targeted for general DSP processors into Register Transfer Level (RTL) VHDL or Verilog code to be mapped onto commercial FPGAs. The Texas Instruments C6000 DSP processor architecture is chosen as the DSP processor platform, and the Xilinx Virtex II as a target FPGA. Various optimizations are discussed, including data dependency analysis, procedure extraction, induction variable analysis, memory optimizations, and scheduling. Experimental results on resource usage and performance are shown for ten software binary benchmarks. Results show performance gains of 3-20X in the FPGA designs over that of the DSP processors in terms of reductions of execution cycles.

Most practical FPGA designs of digital signal processing applications are limited to fixed-point arithmetic owing to the cost and complexity of floating-point hardware. While mapping DSP applications onto FPGAs, a DSP algorithm designer, who often develops his applications in MATLAB, must determine the dynamic range and desired precision of input, intermediate and output signals in a design implementation to ensure that the algorithm fidelity criteria are met. The first step in a flow to map MATLAB applications into hardware is the conversion of the floating-point MATLAB algorithm into a fixed-point version. This paper describes an approach to automate this conversion, for mapping to FPGAs by profiling the expected inputs to estimate errors. Our algorithm attempts to minimize the hardware resources while constraining the quantization error within a specified limit.

In this paper we discuss the problem of interface synthesis for a system on a chip (SoC) such that the power consumption is minimized under some given latency constraints. Since the AMBA protocol has become one of the standard interfaces for SoC cores, we develop our interface synthesis methods around the AMBA protocol. We first provide an analysis of the parameters of the AMBA bus and the communication protocols and a bus power model that will be used by various transformations. Several latency improving and power minimizing transformations are presented at the bus level. Finally, a heuristic is presented which applies the above transformations in a certain order to provide minimum power under a given latency constraint. Experimental results are reported on two example benchmarks in that show that the heuristic is able to reduce power consumption on the wires by about 28% on the average from an initial design having a single layer bus architecture.

Applications that require digital signal processing (DSP) functions are typically mapped onto general purpose DSP processors. With the introduction of advanced FPGA architectures with built-in DSP support, a new hardware alternative is available for DSP designers. By exploiting its inherent parallelism, it is expected that FPGAs can outperform DSP processors. However, the migration of assembly code to hardware is typically a very arduous process. This paper describes the process and considerations for automatically translating software assembly and binary codes targeted for general DSP processors into register transfer level (RTL) VHDL or Verilog code to be mapped onto commercial FPGAs. The Texas instruments C6000 DSP processor architecture has been used as the DSP processor platform, and the Xilinx Virtex II as the target FPGA. Various optimizations are discussed, including loop unrolling, induction variable analysis, memory and register optimizations, scheduling and resource binding. Experimental results on resource usage and performance are shown for ten software binary benchmarks in the signal processing and image processing domains. Results show performance gains of 3-20x in terms of reductions in execution cycles and 1.3-5x in terms of reductions in execution times for the FPGA designs over that of the DSP processors in terms of reductions in execution cycles.

This paper describes an approach for high-level estimation of area, delay and power for FPGA synthesis. This approach has been integrated within the PACT compiler framework which has an automated design space exploration pass that determines the effects of various compiler optimizations on the synthesized hardware. Such a pass needs early estimation of area, delay and power. Towards this end, we have developed area and delay models for various RTL level operators such as adders, multipliers, and logical operators, which are parameterized with the bit widths of the devices. We have also derived high-level equation based power macro-models which take into account input switching activities, input spatial correlation and input bit width. These models are derived by actual synthesis of the RTL operators using back-end logic synthesis and place-and-route tools. Experimental results show that these area, delay and power models are accurate and efficient.

Most practical FPGA designs of digital signal processing applications are limited to fixed-point arithmetic owing to the cost and complexity of floating-point hardware. While mapping DSP applications onto FPGAs, a DSP algorithm designer, who often develops his applications in MATLAB, must determine the dynamic range and desired precision of input, intermediate and output signals in a design implementation to ensure that the algorithm fidelity criteria are met. The first step in a flow to map MATLAB applications into hardware is the conversion of the floating-point MATLAB algorithm into a fixed-point version using quantizers from the Filter Design and Analysis (FDA) Toolbox for MATLAB. We describe an approach to automate the conversion of floating-point MATLAB programs into fixed-point, for mapping to FPGAs by profiling the expected inputs to estimate errors. Our algorithm attempts to minimize the hardware resources while constraining the quantization error within a specified limit.

As more and more complex applications are implemented on FPGAs, high-level design tools are needed to reduce the design time. A good high-level synthesis tool usually has an automated design space exploration pass to determine the effects of various compiler optimizations on the area and power of the synthesized hardware. Such a pass needs early estimation of area and power. Towards this end, we have developed high-level equation based area and power macro-models for various RTL level operators such as adders, multipliers, and logical operators. The area model is parameterized with the bit width of the device and the power model takes into account input switching activity and input spatial correlation as well as input bit width. These models are derived by actual synthesis of these RTL operators using back-end logic synthesis and place-and-route tools. Compared with the other approaches, our method generated a uniform macro-model for each operator with fewer coefficients and sometimes lower degrees. It is also easier to analyze the power sensitivity to different parameters. Experimental results show that these area and power models are accurate and efficient.

Migration of software from older general purpose embedded processors onto newer mixed hardware/software Systems-On-Chip (SOC) platforms is becoming an increasingly important topic. Automatic translation of general purpose software binaries and assembly code onto hardware implementations using FPGAs require sophisticated scheduling and allocation algorithms to maximize the resource utilization of such hardware devices. This paper describes the effects of scheduling and chaining of node operations in a CDFG onto an FPGA. The effects of register allocation on scheduled nodes are also discussed. The Texas Instruments C6000 DSP processor architecture was chosen as the DSP processor platform and assembly code, and the Xilinx Virtex II XC2V250 was chosen as the target FPGA. Results are reported on ten benchmarks, which show that scheduling with chaining operations produces the best results on FPGAs, while the addition of register allocation in fact generates poorer designs in terms of area and frequency.

This paper describes a behavioral synthesis tool called AccelFPGA which reads in high-level descriptions of digital signal processing (DSP) applications written in MATLAB, and automatically generates synthesizable register transfer level (RTL) models and simulation testbenches in VHDL or Verilog. The RTL models can be synthesized using commercial logic synthesis tools and place and route tools onto field-programmable gate arrays (FPGAs). This paper describes how powerful directives are used to provide high-level architectural tradeoffs for the DSP designer. Experimental results are reported on a set of eight MATLAB benchmarks that are mapped onto the Xilinx Virtex II and Altera Stratix FPGAs.

This paper describes a behavioral synthesis tool called the MATCH compiler developed as part of the DARPA Adaptive Computing Systems program. The MATCH compiler reads in high-level descriptions of DSP applications written in MATLAB, and automatically generates synthesizable RTL models in VHDL. The RTL models can be synthesized using commercial logic synthesis tools and place and route tools onto FPGAs. By linking the two design domains of DSP and FPGA hardware design, the MATCH compiler provides DSP design teams a significant reduction in design labor and time, elimination of misinterpretations and costly design rework, automatic verification of the hardware implementation, and the ability of systems engineers and algorithm developers to perform architectural exploration in the early phases of their development cycle. The paper describes how powerful directives are used to provide high-level architectural tradeoffs for the DSP designer. The MATCH compiler has been transferred to a startup company called AccelChip which has developed a commercial version of the compiler called AccelFPGA. Experimental results are reported using AccelFPGA on a set of nine MATLAB benchmarks that are mapped onto the recent Xilinx Virtex II and Altera Stratix FPGAs. The benchmark programs range in complexity from 20 lines to 170 lines of MATLAB code and produce VHDL code ranging from 1500 to 4500 lines of code. The compilation times range from 3 seconds to 40 seconds.

The Adaptive Computing Systems (ACS) program was initiated by Defense Advanced Research Projects Agency (DARPA) of the United States in 1996. With the advent of FPGAs, has emerged a new class of computing systems that contain configurable hardware. This session begins by a presentation by the first ACS program manager of its motivation, original goals, and objectives. It is then followed by presentations of four specific projects under the ACS program. Future activities surrounding the ACS community will be discussed at the end.

This paper describes how the floating point computations in MATLAB can be automatically converted to a fixed point MATLAB version of specific precision for hardware design. The techniques have been incorporated in the AcelFPGA behavioral synthesis tool (Banerjee et al., 2003) that reads in high-level descriptions of DSP applications written in MATLAB, and automatically generate synthesizable RTL models in VHDL or Verilog. Experimental results are reported with the AccelFPGA version 1.5 compiler on a set of five MATLAB benchmarks that are mapped onto the Xilinx Virtex II FPGAs (field programmable gate arrays).

Use of hand optimized Intellectual Property (IP) logic cores is prolific in hardware design. These IP cores range from rather complicated signal processing transforms and filters to arithmetic operators. While IP cores remain a standard way to utilize the improvement in FPGA technology and contend with time to market pressure through reuse, popularity of tools generating hardware descriptions from high-level languages is increasing in popularity. The PACT HDL behavioral synthesis tool attempts to combine these two methods within a power-aware framework. PACT HDL generates RTL HDL codes in VHDL and Verilog using a finite state machine (FSM) style. These codes use intrinsic operators to represent calculations such as addition, subtraction, and multiplication. The output HDL codes are passed to commercial RTL synthesis tools that generate the gate-level hardware descriptions. Each intrinsic operator is replaced with a hardware implementation of the calculation by the synthesis tool. Unfortunately, by leaving this decision to the synthesis tool, the gate-level instantiation may not be appropriate for the desired constraints, particularly those relating to power consumed. The synthesis tools tend to use combinational implementations that are area and power hungry. In some cases, the tool may not be able to instantiate the appropriate logic, such as the division operator, at all.

Applications such as digital cell phones, 3G wireless receivers, and voice over IP, require DSP functions that are typically mapped onto general purpose DSP processors. With the introduction of advanced FPGA architectures which provide built-in DSP support such as the Xilinx Virtex-II, and the Altera Stratix, a new hardware alternative is available for DSP designers. DSP design has traditionally been divided into algorithm development and hardware/software implementation. The majority of DSP algorithm developers use the MATLAB language for prototyping their DSP algorithm. Hardware design teams take the specifications in MATLAB code and manually create an RTL model in VHDL or Verilog. This paper describes how area-performance tradeoffs can be performed quickly at the high-level using a behavioral synthesis tool called AccelFPGA which reads in high-level descriptions of DSP applications written in MATLAB, and automatically generates synthesizable RTL models in VHDL or Verilog. Experimental results are reported with the AccelFPGA compiler on a set of 8 MATLAB benchmarks that are mapped onto the Xilinx Virtex II and Altera Stratix FPGAs.

Use of hand optimized Intellectual Property (IP) logic cores is prolific in hardware design. While IP cores remain a standard way to utilize the improvement in FPGA technology and contend with time to market pressure through reuse, popularity of tools generating hardware descriptions from high-level languages is also increasing in popularity. PACT HDL combines these two methods within a power-aware framework. The PACT HDL compiler generates power optimized VHDL/Verilog from a C language description. This work presents an automated framework to incorporate arbitrary IP logic cores into the C to HDL flow. Thus, PACT HDL can leverage IP cores corresponding to C intrinsic operators. The logic cores to be used are specified by the user through compiler directives or compiler command line options. The framework is power-aware through use of an automated clock-gating technique to "turn off" the IP cores when not in use. The validity of the approach is demonstrated using several image and signal processing benchmarks with a variety of multiplier and divider implementations on a Xilinx Virtex FPGA.

Static array storage optimization in MATLAB.

Algorithm-based fault tolerance (ABFT) is a technique to provide system level error detection and correction on array processors as well as multiprocessors at a low cost. Since the early 1980s the technique has been extensively applied to several linear algebraic algorithms, e.g., matrix multiplication, Gaussian elimination, QR factorization, and singular value decompositions, etc. An important class of problems in numerical linear algebra dealing with the iterative solution of linear algebraic equations arising due to the finite difference discretization or the finite element discretization of a partial differential equation, however, has been overlooked. The only exception is the recent application of algorithm based error detection (ABED) encodings to the successive overrelaxation algorithm for Laplace's equation. In this paper, ABED is applied to a multigrid algorithm for the iterative solution of a Poisson equation in two dimensions. Invariants are created to implement checking in the relaxation, the restriction, and the interpolation operators. Modifications to invariants due to roundoff errors accumulated within the operators, which often lead to a situation known as false alarms, have been addressed by deriving the expressions for the roundoff errors in the algebraic processes in the operators and correcting the invariants accordingly. The ABED encoded multigrid algorithm is shown to be insensitive to the size and the range of the input data besides providing excellent error coverage at a low latency for floating-point, integer, and memory errors.

The performance of applications on large shared-memory multiprocessors with coherent caches depends on the interaction between the granularity of data sharing, the size of the coherence unit, and the spatial locality exhibited by the applications, in addition to the amount of parallelism in the applications. Large coherence units are helpful in exploiting spatial locality, but worsen the effects of false sharing. A mathematical framework that allows a clean description of the relationship between spatial locality and false sharing is derived in this paper. First, a technique to identify a severe form of multiple-writer false sharing is presented. The importance of the interaction between optimization techniques aimed at enhancing locality and the techniques oriented toward reducing false sharing is then demonstrated. Given the conflicting requirements, a compiler-based approach to this problem holds promise. This paper investigates the use of data transformations in addressing spatial locality and false sharing, and derives an approach that balances the impact of the two. Experimental results demonstrate that such a balanced approach outperforms those approaches that consider only one of these two issues. On an eight-processor SGI/Cray Origin 2000 multiprocessor, our approach brings an additional 9 percent improvement over a powerful locality optimization technique that uses both loop and data transformations. The presented approach also obtains an additional 19 percent improvement over an optimization technique that is oriented specifically toward reducing false sharing. This study also reveals that, in addition to reducing synchronization costs and improving the memory subsystem performance, obtaining large granularity parallelism is helpful in balancing the effects of enhancing locality and reducing false sharing, rendering them compatible.

Chip fabrication technology continues to plunge deeper into sub-micron levels requiring hardware designers to utilize ever-increasing amounts of logic and shorten design time. Toward that end, high-level languages such as C/C++ are becoming popular for hardware description and synthesis in order to more quickly leverage complex algorithms. Similarly, as logic density increases due to technology, power dissipation becomes a progressively more important metric of hardware design. PACT HDL, a C to HDL compiler, merges automated hardware synthesis of high-level algorithms with power and performance optimizations and targets arbitrary hardware architectures, particularly in a System on a Chip (SoC) setting that incorporates reprogrammable and application-specific hardware. PACT HDL is intended for applications well suited to custom hardware implementation such as image and signal processing codes. By making the compiler modular and flexible, optimizations may be executed in any order and at different levels in the compilation process. PACT HDL generates industry standard HDL codes, such as RTL Verilog and VHDL, which may be synthesized and profiled for power using commercial tools. This is the first paper on the PACT compiler project in a series. The compiler framework and introductory optimizations are presented. Later papers will focus on these and other optimizations in detail.

We present an area and delay estimator in the context of a compiler that takes in high level signal and image processing applications described in MATLAB and performs automatic design space exploration to synthesize hardware for a field programmable gate array (FPGA) which meets the user area and frequency specifications. We present an area estimator which is used to estimate the maximum number of configurable logic blocks (CLBs) consumed by the hardware synthesized for the Xilinx XC4010 from the input MATLAB algorithm. We also present a delay estimator which finds out the delay in the logic elements in the critical path and the delay in the interconnects. The total number of CLBs predicted by us is within 16% of the actual CLB consumption and the synthesized frequency estimated by us is within an error of 13% of the actual frequency after synthesis through Synplify logic synthesis tools and after placement and routing through the XACT tools from Xilinx. Since the estimators proposed by us are fast and accurate enough, they can be used in a high level synthesis framework like ours to perform rapid design space exploration.

In this paper, we present approaches and algorithms for parallelization of compiled event driven VHDL simulations on shared-memory multiprocessors (SMP). An efficient single-threaded algorithm for simulation of VHDL descriptions is first presented. This algorithm is shown to be competitive with a commercial VHDL simulator. Schemes for multithreaded execution of this algorithm are then described. These have been implemented on top of the POSIX pthreads library and experimental results have been shown on a Sun SparcServer 1000E. Speedups of up to four on eight processors have been achieved for some benchmarks.

We present a compiler that takes high level algorithms described in MATLAB and generates an optimized hardware for an FPGA with external memory. A framework is described to detect and exploit opportunities to pipeline loops in an optimal way. Effectiveness of the framework is demonstrated by synthesizing some image and signal processing applications. Starting from the MATLAB description of the applications, hardware is synthesized that runs on a Xilinx XC4028. The synthesized designs are equivalent to manually optimized designs in performance.

We present a compiler that takes high level signal and image processing algorithms described in MATLAB and generates an optimized hardware for an FPGA with external memory. We propose a precision analysis algorithm to determine the minimum number of bits required by an integer variable and a combined precision and error analysis algorithm to infer the minimum number of bits required by a floating point variable. Our results show that on average, our algorithms generate hardware requiring a factor of 5 less FPGA resources in terms of the configurable logic blocks (CLBs) consumed as compared to the hardware generated without these optimizations. We show that our analysis results in the reduction in the size of lookup tables for functions like sin, cos, sqrt, exp etc. Our precision analysis also enables us to pack various array elements into a single memory location to reduce the number external memory accesses. We show that such a technique improves the performance of the generated hardware by an average of 35%.

Efficient high level design tools that can map behavioral descriptions to FPGA architectures are one of the key requirements to fully leverage FPGA for high throughput computations and meet time-to-market pressures. We present a compiler that takes as input algorithms described in MATLAB and generates RTL VHDL. The RTL VHDL then can be mapped to FPGAs using existing commercial tools. The input application is mapped to multiple FPGAs by parallelizing the application and embedding communication and synchronization primitives automatically. Our compiler infers the minimum number of bits required to represent the variable through a precision analysis framework. The compiler can leverage optimized IP cores to enhance the hardware generated. The compiler also exploits parallelism in the input algorithm by pipelining in the presence of resource constraints. We demonstrate the utility of the compiler by synthesizing hardware for a couple of signal/image processing algorithms and comparing them with manually designed hardware.

This paper presents a novel technique to perform global optimization of communication and preprocessing calls in the presence of array accesses with arbitrary subscripts. Our scheme is presented in the context of automatic parallelization of sequential programs to produce message passing programs for execution on distributed machines. We use the static single assignment (SSA) form for message passing programs as the intermediate representation and then present techniques to perform global optimizations even in the presence of array accesses with arbitrary subscripts. The focus of this paper is in showing that, using a uniform compilation method both at compile-time and at run-time, our framework is able to determine the earliest and the latest legal communication point for a certain distributed array reference even in the presence of arbitrary array addressing functions. Our scheme then heuristically determines the final communication point after considering the interaction between the relevant communication schedules. Owing to combined static and dynamic analysis, a quasi-dynamic method of code generation is implemented. We describe the need for proper interaction between the compiler and the run-time routines for efficient implementation of optimizations as well as for compatible code generation. All of the analyses is initiated at compile-time, static analyses of the program is done as much as possible, and then the run-time routines take over the analyses while building on the data structures initiated at compile time. This scheme has been incorporated in our compiler framework which can use uniform methods to compile, parallelize, and optimize a sequential program irrespective of the subscripts used in array addressing functions. Experimental results for a number of benchmarks on an IBM SP-2 show up to around 10-25% reduction in total run-times in our globally-optimized schemes compared to other state-of-the-art schemes on 16 processors.

Exploiting locality of references has become extremely important in realizing the potential performance of modern machines with deep memory hierarchies. The data access patterns of programs and the memory layouts of the accessed data sets play a critical role in determining the performance of applications running on these machines. This paper presents a cache locality optimization technique that can optimize a loop nest even if the arrays referenced have different layouts in memory. Such a capability is required for a global locality optimization framework that applies both loop and data transformations to a sequence of loop nests for optimizing locality. Our method uses a single linear algebra framework to represent both data layouts and loop transformations. It computes a nonsingular loop transformation matrix such that, in a given loop nest, data locality is exploited in the innermost loops, where it is most useful. The inverse of a nonsingular transformation matrix is built column-by-column, starting from the rightmost column. In addition, our approach can work in those cases where the data layouts of a subset of the referenced arrays is unknown; this is a key step in optimizing a sequence of loop nests and whole programs for locality. Experimental results on an SGI/Cray Origin 2000 nonuniform memory access multiprocessor machine show that our technique reduces execution times by as much as 70 percent.

Large time-constrained applications are highly computer-intensive and are often implemented as a complex organization of pipelined data parallel tasks on a pool of embedded processors, DSP processors, and FPGAs. The large number of design alternatives available at each task level, the application as a whole, and the special needs of the reconfigurable devices (such as the FPGA) make the manual synthesis of such systems very tedious. The automatic synthesis algorithm in this paper combines exact (MILP-based) and heuristic techniques to solve this problem, which basically involves (1) propagation of timing constraints; (2) pipelining the loops to meet throughput requirements; (3) resource selection and scheduling, keeping the processing requirements and the timing constraints in view; (4) scheduling the resources across the tasks to ensure maximum utilization; and (5) hiding the reconfiguration delays of the FPGAs. While the use of MILP techniques helps in getting high-quality results, combining them with heuristics ensures acceptable synthesis times, striking a good balance between quality of results and synthesis time. Our experimental evaluation of the algorithm shows an average 40% in resource cost reduction (compared to manual synthesis) with synthesis times from minutes to as low as a few seconds in some cases.

Ownership sets are fundamental to the partitioning of program computations across processors by the owner-computes rule. These sets arise due to the mapping of arrays onto processors. In this paper, we focus on how ownership sets can be efficiently determined in the context of the HPF language and show how the structure of these sets can be symbolically characterized in the presence of arbitrary array alignment and array distribution directives. Our starting point is a system of equalities and inequalities due to Ancourt et al. (1995) that captures the array mapping problem in HPF. We arrive at a refined system that enables us to efficiently solve for the ownership set using the Fourier-Motzkin Elimination technique and that requires the course vector as the only auxiliary vector. The formulation makes it possible to enumerate the elements of the ownership set exactly once, a feature that is very beneficial when such sets are applied to handle DO loops qualified by HPF's INDEPENDENT directive. We develop important and general properties pertaining to HPF alignments and distributions and show how they can be used to eliminate redundant communication due to array replication. Polynomial-time schemes that determine whether the ownership set of a particular processor, with respect to some array, is the empty set or whether the ownership set of every processor, with respect to some array, is the empty set, are presented. We show how distribution directives with unspecified processor meshes can be efficiently handled at compile time. We also show how to avoid the generation of communication code when pairs of array references are ultimately mapped onto the same processors. Experimental data demonstrating the improved code performance that the latter optimization enables is presented and discussed.

The delivered performance on modern processors that employ deep memory hierarchies is closely related to the performance of the memory subsystem. Compiler optimizations aimed at improving cache locality are critical in realizing the performance potential of powerful processors. For scientific applications, several loop transformations have been shown to be useful in improving both temporal and spatial locality. Recently, there has been some work in the area of data layout optimizations, i.e., changing the memory layouts of multidimensional arrays from the language-defined default such as column-major storage in Fortran. The effect of such memory layout decisions is on the spatial locality characteristics of loop nests. While data layout transformations are not constrained by data dependences, they have no effect on temporal locality. On the other hand, loop transformations are not readily applicable to imperfect loop nests and are constrained by data dependences. More importantly, loop transformations affect the memory access patterns of all the arrays accessed in a loop nest and, as a result, the locality characteristics of some of the arrays may worsen. This paper presents a technique based on integer linear programming (ILP) that attempts to derive the best combination of loop and data layout transformations. Prior attempts to unify loop and data layout transformations for programs consisting of a sequence of loop nests have been based on heuristics not only for transformations for a single loop nest but also for the sequence in which loop nests will be considered. The ILP formulation presented here obviates the need for such heuristics and gives us a bar against which the heuristic algorithms can be compared. More importantly, our approach is able to transform memory layouts dynamically during program execution. This is particularly useful in applications whose disjoint code segments demand different layouts for a given array. In addition, we show how this formulation can be extended to address the false sharing problem in a multiprocessor environment. The key data structure we introduce is the memory layout graph (MLG) that allows us to formulate the problems as path problems. The paper discusses the relationship of this ILP approach based on the memory layout graphs to other work in the area including our previous work. Experimental results on a MIPS R10000-based system demonstrate the benefits of this approach and show that the use of the ILP formulation does not increase the compilation time significantly.

We p r e s e n t a high-level synthesis framework to synthesize optimized hardware on FPGAs from algorithms described in MATLAB.We focus on a framework to pipeline loops present in the input application.We present a range of scheduling algorithms to obtain the pipeline schedule and discuss their comparative strengths.The synthesized hardwares have been mapped to a Xilinx XC4028 FPGA with external memory and corresponding experimental results are included.Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page.To copy

Recently a number of heuristic based system-level synthesis algorithms have been proposed. Though these algorithms quickly generate good solutions, how close these solutions are to optimal is a question that is difficult to answer. While current exact techniques produce optimal results, they fail to produce them in reasonable time. This paper presents a synthesis algorithm that produces solutions of guaranteed quality (optimal in most cases or within a known bound) with practical synthesis times (few seconds to minutes). It takes a unified look (the lack of which is one of the main sources of sub-optimality in the heuristic techniques) at different aspects of system synthesis such as pipelining, selection, allocation, scheduling and FPGA reconfiguration. Our technique can handle both time constrained as well as resource constrained synthesis problems. We present results of our algorithm implemented as part of the Match project at Northwestern University.

Recently, high-level languages such as MATLAB have become popular in prototyping algorithms in domains such as signal and image processing. Many of these applications whose subtasks have diverse execution requirements, often employ distributed, heterogeneous, reconfigurable systems. These systems consist of an interconnected set of heterogeneous processing resources that provide a variety of architectural capabilities. The objective of the MATCH (MATLAB Compiler for Heterogeneous Computing Systems) compiler project at Northwestern University is to make it easier for the users to develop efficient code for distributed heterogeneous, reconfigurable computing systems. Towards this end we are implementing and evaluating an experimental prototype of a software system that will take MATLAB descriptions of various applications, and automatically map them on to a distributed computing environment consisting of embedded processors, digital signal processors and field-programmable gale arrays built from commercial off-the-shelf components. We provide an overview of the MATCH compiler and discuss the testbed which is being used to demonstrate our ideas. We present preliminary experimental results on some benchmark MATLAB programs with the use of the MATCH compiler.

This paper describes a C compiler for a mixed Processor/FPGA architecture where the FPGA is a Reconfigurable Functional Unit (RFU). It presents three compilation techniques that can extract computations from applications to put into the RFU. The results show that large instruction sequences can be created and extracted by these techniques. An average speedup of 2.6 is achieved over a set of benchmarks.

Fast FPGA CAD tools that produce high quality results has been one of the most important research issues in the FPGA domain. Simulated annealing has been the method of choice for placement. However, simulated annealing is a very compute-intensive method. In our present work we investigate a range of parallelization strategies to speedup simulated annealing with application to placement for FPGA. We present experimental results obtained by applying the different parallelization strategies to the Versatile Place and Route (VPR) Tool, implemented on an SGI Origin shared memory multi-processor and an IBM-SP2 distributed memory multi-processor. The results show the tradeoff between execution time and quality of result for the different parallelization strategies.

Very fast and accurate 3-D capacitance extraction is essential for ultra deep sub-micron design (UDSM) of integrated circuits. Parallel processing provides an approach to reducing the simulation turn-around time. In this paper, we present two parallel formulations for 3-D capacitance extraction, based on the fast multipole method (FMM) and the direct boundary element method (BEM), respectively. We report detailed comparison results on parallel efficiency and memory scalability, on three different distributed memory platforms, including a 16 processor IBM SP2, and ATM network of 16 HP workstations, and an Ethernet network of 16 HP workstations.

MATLAB is one of the most popular languages for desktop numerical computations as well as for signal and image processing applications. Applying parallel processing techniques to improve performance of MATLAB codes has been the goal of many recent works. Most current frameworks require the user to specify parallelism and/or information regarding type/shape of the variables, thereby sacrificing the user friendliness which is one of the most popular MATLAB features. Other systems work on a restricted subset of MATLAB, thereby limiting the class of applications MATLAB can support. We present a runtime system capable of executing MATLAB code in parallel without any user intervention. The runtime system performs automatic parallelization and type/shape inference of the code at runtime. A unique feature of the runtime system is its capability to automatically adapt to changes in the underlying architecture, making it particularly useful for systems where predicting performance statically is difficult. We present experimental results obtained for the runtime system running on SGI Origin2000 shared memory multiprocessor.

We present a fine-grained parallel processing scheme for speeding up an industrial VLSI synthesis tool on a network of workstations without sacrificing the quality of results. The synthesis tool is Ambit BuildGates, a high-capacity ASIC logic synthesis software from Cadence Design Systems. We examine some necessary operating conditions for a practical parallel implementation of such a software, and propose a parallel approach which accommodates for the highly-irregular computation requirements in synthesis and the high-latency, low-bandwidth conditions of the target environment. For pragmatic as well as performance concerns, we designed a parallel algorithm which produces results (synthesized logic) that are identical to those of the original uniprocessor algorithm. We employ heuristic load assessment and adaptive cyclic distribution in order to actively balance the unpredictable load throughout execution, which enables a considerable reduction in runtime (i.e. 51.3 hours down to 23.4 hours) on actual customer design benchmarks.

Very fast and accurate 3-D capacitance extraction is essential for interconnect optimization in ultra deep sub-micro designs (UDSM). Parallel processing provides an approach to reducing the simulation turn-around time. This paper examines the parallelization of the well known fast multipole based 3-D capacitance extraction program FASTCAP, which employs new preconditioning and adaptive techniques. To account for the complicated data dependencies in the unstructured problems, we propose a generalized cost function model, which can be used to accurately measure the workload associated with each cube in the hierarchy. We then present two adaptive partitioning schemes, combined with efficient communication mechanisms with bounded buffer size, to reduce the parallel processing overhead. The overall load balance is achieved through balancing the load at each level of the multipole computation. We report detailed performance results using a variety of standard benchmarks on 3-D capacitance extraction, on an IBM SP2.

Reconfigurable hardware has the potential for significant performance improvements by providing support for application-specific operations. We report our experience with Chimaera, a prototype system that integrates a small and fast reconfigurable functional unit (RFU) into the pipeline of an aggressive, dynamically-scheduled superscalar processor. Chimaera is capable of performing 9-input/1-output operations on integer data. We discuss the Chimaera C compiler that automatically maps computations for execution in the RFU. Chimaera is capable of: (1) collapsing a set of instructions into RFU operations, (2) converting control-flow into RFU operations, and (3) supporting a more powerful fine-grain data-parallel model than that supported by current multimedia extension instruction sets (for integer operations), Using a set of multimedia and communication applications bye show that even with simple optimizations. The Chimaera C compiler is able to map 22% of all instructions to the RFU on the average. A variety of computations are mapped into RFU operations ranging from as simple as add/sub-shift pairs to operations of more than 10 instructions including several branches. Timing experiments demonstrate that for a 4-way out-of-order superscalar processor Chimaera results in average performance improvements of 21%, assuming a very aggressive core processor design (most pessimistic RFU latency model) and communication overheads from and to the RFU.

Minimizing communication and synchronization costs is crucial to the realization of the performance potential of parallel computers. This paper presents a general technique which uses a global data-flow framework to optimize communication and synchronization in the context of the one-way communication model. In contrast to the conventional send/receive message-passing communication model, one-way communication is a new paradigm that decouples message transmission and synchronization. In parallel machines with appropriate low-level support, this may open up new opportunities not only to further optimize communication, but also to reduce the synchronization overhead. We present optimization techniques using our framework for eliminating redundant data communication and synchronization operations. Our approach works with the most general data alignments and distributions in languages like High Performance Fortran (HPF) and uses a combination of the traditional data-flow analysis and polyhedral algebra. Empirical results for several scientific benchmarks on a Cray T3E multiprocessor machine demonstrate that our approach is successful in reducing the number of data (communication) and synchronization messages, thereby reducing the overall execution times.

This paper starts from a well-known idea, that structure in irregular problems improves sequential performance, and tries to show that the same structure can also be exploited for parallelization of irregular problems on a distributed-memory multicomputer. In particular, we extend a well-known parallelization technique called run-time compilation to use structure information that is explicit on the array subscripts. This paper presents a number of internal representations suited to particular access patterns and shows how various preprocessing structures such as translation tables, trace arrays, and interprocessor communication schedules can be encoded in terms of one or more of these representations. We show how loop and index normalization are important for detection of irregularity in array references, as well as the presence of locality in such references. This paper presents methods for detection of irregularity, feasibility of inspection, and finally, placement of inspectors and interprocessor communication schedules. We show that this process can be automated through extensions to an HPF/Fortran-77 distributed-memory compiler (PARADIGM) and a new runtime support for irregular problems (PILAR) that uses a variety of internal representations of communication patterns. We devise performance measures which consider the relationship between the inspection cost, the execution cost, and the number of times the executor is invoked so that a comparison of the competing schemes can be performed independent of the number of iterations. Finally, we show experimental results on an IBM SP-2 that validate our approach. These results show that dramatic improvements in both memory requirements and execution time can be achieved by using these techniques.

Variants of delay-cost functions have been used in a class of technology mapping algorithms [l, 2, 3, 41.We illustrate that in an industrial environment the delay-cost function can grow unboundedly and lead to very large runtimes.The key contribution of this work is a novel bounded compression algorithm.We introduce a concept of a delaycost curve, (o-DC-curve)that requires upto exponentially less delay-cost points to be stored compared to that stored by the delay function.We prove that the solution obtained by this exponential compaction of the delay-function is bounded to cy% of the optimal solution.We also suggest a large set of CAD applications which may benefit from using Q-DC-curve.Finally, we demonstrate the effectiveness of our compaction scheme on one such application, namely technology mapping for low power.Experimental results on industrial environment show that we are more than 17 times faster than [2] on certain MCNC circuit.

One of the foremost problems in physical design for deep-submicron circuits is the need for estimates that depend on future decisions. Estimation of area, timing, and coupling are required. We propose a novel floorplanner, with a new wiring metric, which can be updated quickly in small increments. This provides tools with a way to influence the floorplan as they make changes without large running time penalty. We provide experimental results that show the incremental approach to be generally 5 times faster than full floorplanning while maintaining good estimates.

In this paper we discuss the 3-Dimensional (3-D) capacitance and resistance extraction within an iterative design environment, where small changes are made to the 3-D structures. We present a bounded incremental algorithm for accurate and fast 3-D extraction in such a design environment, based on the Boundary Element Method (BEM). The incremental algorithm can re-utilize the computation results of previous extractions and rapidly re-compute the new parasitic parameters in response to the design changes made to the layout. The incremental algorithm has been implemented in the ICE tool. Experimental results on a set of 3-D interconnect structures show that the incremental algorithm is efficient for the iterative design methodology. For one large structure, the incremental extraction is over 20 times faster than the full extraction without using the incremental algorithm. To the best of our knowledge, this is the first reported work on an incremental algorithm for capacitance and resistance extraction.

There has been much work recently on improving the locality performance of loop nests in scientific programs through the use of loop as well as data layout optimizations. However, little attention has been paid to the problem of optimizing locality in whole programs, particularly in the presence of procedures. Current techniques do not propagate layout optimizations across procedures boundaries; this is critical for realistic scientific codes, since the cost of explicitly transforming memory layouts across procedure boundaries might be very high. In this paper we present a locality optimization framework that uses both loop and data transformations to improve cache locality program-wide. Our framework propagates layout (or locality) constraints as a system of equalities across procedures and involves two traversals in the call graph representation of the program. Preliminary experimental results obtained on an R10000 based system demonstrate the power of the framework.

In this paper, we consider delay optimization in multilayer detailed routing. Given a detailed routing by some detailed router, we iteratively improve the delays of critical nets or nets with timing violation in an aggressive way. A rip-up and reroute approach is employed to generate the alter-nate routes. The optimal route which satisfies the timing constraints is chosen. The net delays are calculated us-ing the Elmore delay model. The coupling capacitances are computed using a 3D extractor by applying the process parameters. In such an approach, the interconnect delay can be most accurately modeled. However, this aggressive approach is likely to be computationally unaffordable, be-cause the delay of each alternate route should be evaluated. To overcome this problem, the key is to efficiently handle the detailed 3-D extraction in each iteration step. In our approach, we represent the design changes in an incremen-tal way. Then we compute the coupling capacitance using the incremental extraction algorithm which is specifically tuned to an iterative design environment. This makes the aggressive improvement approach computationally practi-cal. Experimental results are presented to demonstrate the efficiency of the approach. 1.

In this paper, we present some novel algorithms for scheduling hierarchical signal flow graphs in the domain of high-level synthesis. With complex chips that need to be designed in the future, it is expected that the runtimes of these scheduling algorithms will be quite large. The key contributions of this paper are as follows: First, we develop a novel extension of the sequential force-directed scheduling algorithm which naturally handles loops and conditionals by coming up with a scheme of scheduling hierarchical signal flow graphs. Second, we develop three new parallel algorithms for the scheduling problem. Our parallel algorithms are portable across a wide range of parallel platforms. We report results on a set of high-level synthesis benchmarks on 8-processor SGI Origin and a 64 processor IBM SP-2. While some parallel algorithms for VLSI CAD reported by earlier researchers have reported a loss of qualities of results, our parallel algorithms produce exactly the same results as the sequential algorithms on which they are based.

Reducing communication overhead is extremely important in distributed-memory message-passing architectures. In this article, we present a technique to improve communication that considers data access patterns of the entire program. Our approach is based on a combination of traditional data-flow analysis and a linear algebra framework, and it works on structured programs with conditional statements and nested loops but without arbitrary goto statements.The distinctive features of the solution are the accuracy in keeping communication set information, support for general alignments and distributions including block-cyclic distribu-tions, and the ability to simulate some of the previous approaches with suitable modifications. We also show how optimizations such as message vectorization, message coalescing, and redundancy elimination are supported by our framework. Experimental results on several benchmarks show that our technique is effective in reducing the number of messages (anaverage of 32% reduction), the volume of the data communicated (an average of 37%reduction), and the execution time (an average of 26% reduction).

This paper presents a data layout optimization technique for sequential and parallel programs based on the theory of hyperplanes from linear algebra. Given a program, our framework automatically determines suitable memory layouts that can be expressed by hyperplanes for each array that is referenced. We discuss the cases where data transformations are preferable to loop transformations and show that under certain conditions a loop nest can be optimized for perfect spatial locality by using data transformations. We argue that data transformations can also optimize spatial locality for some arrays without distorting temporal/spatial locality exhibited by others. We divide the problem of optimizing data layout into two independent subproblems: 1) determining optimal static data layouts, and 2) determining data transformation matrices to implement the optimal layouts. By postponing the determination of the transformation matrix to the last stage, our method can be adapted to compilers with different default layouts. We then present an algorithm that considers optimizing parallelism and spatial locality simultaneously. Our results on eight programs on two distributed shared-memory multiprocessors, the Convex Exemplar SPP-2000 and the SGI Origin 2000, show that the layout optimizations are effective in optimizing spatial locality and parallelism.

Finding the set of steady states of a machine has applications in formal verification, sequential synthesis and ATPG. Existing techniques assume the presence of a designated set of initial states which is impractical in a real design environment. The set of steady state of a design is defined by the terminally strongly connected components (tSCCs) of the underlying state transition graph (STG). We show that multiple tSCCs and non-terminal SCCs need to be handled in a real design environment especially for verification. We present a fully implicit algorithm to find the steady states of a machine without any knowledge of initial states. We demonstrate the utility of our algorithm by applying it to FSM equivalence checking.

Sev eral tec hniques currently exist for estimating the pow er dissipation of combinational and sequen tialcircuits using exhaustive sim ulation,Monte Carlo sampling, and probabilistic estimation. Exhaustive sim ulation and Monte Carlo sampling techniques can be highly reliable but often require long runtimes. This paper presents a comprehensive study of pattern-p artitioning and circuit-p artitioning parallelization schemes for those tw o methodologies in the con text of distributed-memory multiprocessing systems. Issues in pip eline dev ent-driv en simulation and dynamic load balancing are addressed. Experimental results are presented for an IBM SP-2 system and a netw ork of HP-9000 workstations. F or instance, runtimes have been reduced from over 3 hours to under 20 minutes in one case.

Traditional placement problems are studied under a fully specified cell library and a complete netlist. However, in the first, e.g., 2 years of a 2-3 year microprocessor design cycle, the detailed netlist is unavailable. For area and performance estimation, layout must nevertheless be done with incomplete information. Another source of incompleteness comes from reuse of instances from earlier design generations; these instances and their parameters will change as the project evolves. The problem of placement with incomplete data (PID) can be abstracted as having to place a circuit when p/sub c/% of the cells and p/sub n/% of the nets are missing. The key challenge in PID is how to add missing cells and nets. In this paper, two patching-methods for adding missing nets and cells are proposed. The methods are called abstraction and fusion. Experimental results are very interesting and illustrative. First, they show that PID is a difficult problem and an arbitrary (and perhaps intuitively sound) method may not produce high-quality results. Experiments verify that the abstraction method is a very good predictor and that fusion is not because circuits produced by abstraction attain much of the properties of the original circuits. Summary Table 3 in Section 4 shows that when a circuit has 10% incompleteness, abstraction can predict the final total wirelength with an error of 5.8%, while fusion has a 67.8% error in predicting the wirelength in the same circuit.

This paper describes algebraic techniques that target low power consumption. A unique power cost function based on decomposed factored form representation of a Boolean expression is introduced to guide the structural transformations. Circuits synthesized by the SIS and POSE consume 54.5% and 10.4% more power than that obtained by our tool respectively.

We present a novel framework of a Web-based automated parallel CAD environment. The goal of this project is to make available to the CAD community a growing number of design and test applications that support standard interfaces and execute efficiently in a parallel environment. The design files of a user working on a remote machine are transparently shipped to the local Compute Center, the relevant computation is performed in a parallel environment and then the results are returned back to the user. A job submission and scheduling tool ensures proper load balance and maximal usage of the various parallel machines. The whole process is done efficiently and transparently without the user having to bother about any low-level details. At present, a number of parallel CAD tools including a placement tool, a fault simulator and a VHDL simulator are supported. Results from a preliminary implementation are impressive and show the feasibility of the approach.

The use of multi-phase clocking scheme, aggressive pipelining and #sparse" encodings in high performance designs results in a tremendous increase in the state space. In this paper, we show that automatically transforming such designs to ones that have more #dense" encodings can result in signi#cant bene#ts in using implicit BDD-based techniques for their veri#cation. We formulate a relaxed retiming framework which is more powerful than traditional retiming in reducing the number of latches and show that it can be applied to the product machine model for checking sequential hardware equivalence #SHE# without altering the correctness of the SHE check. We combine retiming with phase abstraction #4# #a technique to transform multi-phase FSMs to single-phase FSMs for equivalence checking#. The two transformations enable the SHE check to be performed on high performance controllers with large state space #more than 100 latches# from an industrial setting. 1 Introduction Due to aggressive t...

The computational complexity of a probability based combinational power metric lies in the creation of a BDD for each node in the circuit. We formalize the problem of finding an intermediate support set which controls the size of BDD. We propose an exact algorithm to solve it. We also propose an heuristic solution, PowerDrive, for estimating the power of large circuits. Apart from being more accurate and several times faster than methods by H. Choi and S.H. Hwang (1997) and B. Kapoor (1994), PowerDrive possesses the unique quality of being canonical and of constant complexity, a very desirable quality for a power metric guiding a synthesis tool. Finally, the proposed power metric was able to guide the synthesis tool (S. Roy et al., 1998) to optimize large circuits which could not be synthesized by POSE (S. Imam and M. Pedram, 1995), thus proving the effectiveness of our power metric.

This paper describes a novel technique of integrating a fast power-driven mapper with structural optimizations that target low power consumption. The power-driven mapping technique is based on the decomposed factored form representation of Boolean expressions. The power cost function based on this mapped netlist is more accurate than the previous cost functions. It is used to guide the structural transformations in our low-power driven logic synthesis tool. Circuits synthesized by the area optimization tool, SIS, consume on an average 54.5% more power and require 21.9% more area than those obtained by our tool. Finally, results obtained from the power optimization tool, POSE, are on the average 10.4% and 5.6% inferior in power consumption and area respectively to those obtained by our tool.

In contrast to the conventional send/receive model, the one-way communication model using Put and Synch allows the decoupling of message transmission from synchronization. This opens up new opportunities not only to further optimize communication but also to reduce synchronization overhead. We present a general technique which uses a global dataflow framework to optimize communication and synchronization in the context of the one-way communication model. Our approach works with the most general data alignments and distributions in languages like HPF, and is more powerful than other current solutions for eliminating redundant synchronization messages. Preliminary results on several scientific benchmarks demonstrate that our approach is successful in minimizing the number of data and synchronization messages.

The timing-driven global routing problem is an extremely important and time consuming phase of any automated layout system. In this paper, by integrating high performance interconnection tree construction, wire-sizing, and switch-able segment channel optimization together, we propose an adaptive timing-driven global routing algorithm which minimizes the timing delay as well as circuit area. Our experiments on MCNC benchmarks show that our timing-driven global routing algorithm reduces the maximum path delays significantly from the global router TimberWolfSC. Based on this adaptive timing-driven global routing algorithm, a parallel algorithm on timing-driven global routing for standard cells is given. This algorithm has been implemented on an 8 processor IBM J-40 shared memory multi-processor by using the Message Passing Interface (MPI). Our experimental results show good speedup and circuit delay results for this parallel algorithm using MCNC benchmark circuits.

Almost all applications containing indirect array addressing (irregular accesses) have a substantial number of direct array accesses (regular accesses) too.A conspicuous percentage of these direct array accesses usually require interprocessor communication for the applications to run on a distributed memory multicomputer.This study highlights how lack of a uniform representation and lack of a uniform scheme to generate communication structures and parallel code for regular and irregular accesses in a mixed regularirregular application prevent sophisticated optimizations.Furthermore, we also show that code generated for regular accesses using compile-time schemes are not alzvays compatible to code generated for irregular accesses using run-time schemes.In our opinion, existing schemes handling mixed regular-irregular applications either incur unnecessary preprocessing costs or fail to perform the best communication optimization.This study presents a uniform scheme to handle both regular and irregular accesses in a mixed regularirregular application.While this allows for sophisticated communication optimizations such as message coalescing, message aggregation to be made across regular and irregular accesses, the preprocessing costs incurred are likely to be minimum.Experimental comparisons for various benchmarks on a 16-processor IBM SP-2 show that our scheme is feasible and better than existing schemes.

This paper presents a data layout optimization technique based on the theory of hyperplanes from linear algebra.Given a program, our framework automatically determines the optimal layouts that can be expressed by hyperplanes for each array that is referenced.We discuss the cases where data transformations are preferable to loop transformations and show that under specific conditions a loop nest can be optimized for perfect spatial locality by using data transformations.We divide the problem of optimizing data layout into two independent subproblems: (1) determining optimal layouts, and (2) determining data transformation matrices to implement optimal layouts.By postponing the determination of the transformation matrix to the last stage, our method can be adapted to compilers with different default layouts.Our results on eight programs on SGI Origin 2000 distributed-shared-memory multiprocessor show that the layout optimizations are effective in optimizing spatial locality.

Article Parallel compiled event driven VHDL simulation Share on Authors: V. Krishnaswamy Intel Corporation, JFT 103, 2111, NE 25th Ave, Hillsboro, OR Intel Corporation, JFT 103, 2111, NE 25th Ave, Hillsboro, ORView Profile , P. Banerjee Northwestern University, Center for Parallel and Dist. Computing, 2145 Sheridan Road, Evanston, IL Northwestern University, Center for Parallel and Dist. Computing, 2145 Sheridan Road, Evanston, ILView Profile Authors Info & Claims ICS '98: Proceedings of the 12th international conference on SupercomputingJuly 1998 Pages 297–304https://doi.org/10.1145/277830.277901Online:13 July 1998Publication History 4citation403DownloadsMetricsTotal Citations4Total Downloads403Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In deep sub-micron fabrication technology, clock skew is one of the dominant factors which determine system performance. Previous works in zero skew clock tree routing assume that the wires have uniform size, and previous wire-sizing algorithms for general signal nets do not produce the exact zero skew. In this paper, we first propose an algorithm to get the exact zero skew wire-sizing by using an iterative method to make the wire size improvement. Our experiments on benchmark clock trees show that the algorithm reduces the source sink delay more than 3 times that of the clock trees with uniform wire sizes and keeps the clock skew zero. Motivated by the computation intensive nature of the zero skew clock tree construction and wire-sizing, we propose a parallel algorithm using a cluster-based clock tree construction algorithm and our zero skew wire-sizing algorithm. Without sacrificing the quality of the solution, on the average we obtain speedups of 7.8 from the parallel clustering based clock tree construction algorithm on an 8 processor SUN SPARC Server 1000E shared memory multi-processor.

This paper presents a new integrated compiler framework for improving the cache performance of scientific applications. In addition to applying loop transformations, the method includes data layout optimizations, i.e., those that change the memory layouts of data structures (arrays in this case). A key characteristic of this approach is that loop transformations are used to improve temporal locality while data layout optimizations are used to improve spatial locality. This optimization framework was used with sixteen loop nests from several benchmarks and math libraries, and the performance was measured using a cache simulator in addition to using a single node of the SGI Origin 2000 distributed-shared-memory machine for measuring actual execution times. The results demonstrate that this approach is very effective in improving locality and outperforms current solutions that use either loop or data transformations alone. We expect that our solution will also enable better register usage due to increased temporal locality in the innermost loop, and that it will help in eliminating false-sharing on multiprocessors due to exploiting spatial locality in the innermost loop.

Optimization of large sequential circuits has become unmanageable in CAD of VLSI due to time and memory requirements. We report a parallel algorithm for the state assignment problem for finite state machines. Our algorithm has three significant contributions: it is an asynchronous parallel algorithm portable across different MIMD machines; time and memory requirements reduce linearly with the number of processors, enabling the parallel implementation to handle large problem sizes; and the quality of the results for multiprocessor runs remains comparable to the serial algorithm on which it is based due to an implicit backtrack correction mechanism built into the parallel implementation.

Equivalence checking of finite state machines (FSMs) traditionally assumes single phase machines where a single clock (implicit or explicit) synchronizes the state of the FSM. We extend the equivalence checking paradignm to FSMs with multi-phase clocks. Such designs are becoming increasingly popular in high performance microprocessors since they result in lower synchronization overhead. In addition, aggressive pipelining and the use of “sparse” encodings results in designs where the ratio of steady states to the total state space is very low. In this paper, we show that automatically transforming such designs to ones that have more “dense” encodings can result in significant benefits in using implicit BDD-based techniques for their verification. We explore two such techniques: phase abstraction and retiming and demonstrate their utility in the context of FSM equivalence checking. The main contributions of our work are: —We show that a multi-phase FSM can be transformed to a functionally equivalent one phase FSM and this phase abstraction leads to significant improvement in the size of FSMs that can be checked for equivalence. —We show that min-latch retiming preserves equivalence and can be performed efficiently in multi-phase designs, even when latch borrowing and discarding is allowed at the primary inputs and outputs. —We demonstrate the utility of our approach on several controller FSMs from the industry.

Addresses the problem of software generation from a hardware description language (HDL). In particular, we examine the issues involved in translating VHDL into C or C++ for use in system simulation and cosynthesis. Because of the concurrency supported by VHDL, and a notion of timing behavior, care must be taken to ensure behavioral correctness of the generated software. The issues involved are shown to be different in each of the application areas. The ideas set forth in this paper have been used in an efficient VHDL simulator designed to execute on multiprocessor systems. Results are presented for simulation on uniprocessor as well as multiprocessor systems.

Formally verifying properties of signals in a circuit hasseveral applications in an equivalence checking based formalverification flow.In a hierarchical design, functionalityis divided across blocks.This necessitates the useof constraints on input signals of a block to avoid falsenegatives.Validating such input constraints requires assertionchecking at the outputs of modules generatingthe constrained signals.In this paper, we present anefficient assertion checker for combinational propertieswhich avoids the BDD explosion problem by finding anoptimal intermediate correlation free frontier.It hasbeen successfully used in an industrial setting to uncovera number of bugs.

Simulated annealing based standard cell placement for VLSI designs has long been acknowledged as a compute-intensive process. All previous work in parallel simulated annealing based placement has minimized area, but with deep submicron design, minimizing wirelength delay is also needed. The algorithm discussed in this paper is the first parallel algorithm for timing driven placement. We have used a very accurate Elmore delay model which is more complete intensive and hence the need for parallel placement is more apparent. Parallel placement is also needed for very large circuits that may not fit in the memory of a single processor. Therefore, our algorithm is circuit partitioned and can handle arbitrary large circuits on distributed memory multiprocessors. The algorithm, called mpi PLACE, has been tested on several large benchmarks on a variety of parallel architectures.

Edge detection and shape detection in digital images are very computationally intensive problems. Parallel algorithms can potentially provide significant speedups while preserving the quality of the result obtained. Hough and Radon Transforms are projection-based transforms which are commonly used for edge detection and shape detection respectively. We propose in this paper various new parallel algorithms which exploit both task and data parallelism available in Hough and Radon transforms algorithms. A memory scalable aggressive task parallel algorithm is shown to be the most optimal algorithm in terms of memory scalability and performance on an IBM SP2.

In this paper, we propose a unique problem in the assignment of overlapping tasks to processors on a parallel machine, with the twin objectives of minimizing workloads while maintaining good load balance. This problem arises in some applications in VLSI CAD, e.g. parallel compiled VHDL simulation. We assume that the parallel application can be decomposed into a set of tasks, each in turn comprising a finite number of subtasks. Overlapped computations arise as a result of replication of subtasks across tasks in order to reduce the amount of communication performed in fine grained parallel applications. The uniqueness of the problem stems from the fact that overlapping computation on tasks assigned to the same processor is only performed once. Theoretical results on NP-hardness and bounds on the utilization of overlap are provided. A heuristic solution is also proposed. An important application area in VLSI-CAD, parallel compiled event driven VHDL simulation is introduced. Results of the application of our heuristics to this problem are reported on a SUN Sparcserver 1000 multiprocessor.

This paper presents a detailed evaluation of parallel mesaagedriven pmgmms on both message-passing and shared memory pamllel architectures.Four large pomllel appiications from the domain of VLSI computer aided design are evaluated, namely: parallel test pattern genemtion, pamllel cell placement, logic qnthesis, and event dn'ven VHDL kmulalion.The parallelism structure, the communication characterktics, locality chamcterirrtics, gmin sizes of wmputationa, and detailed measurement8 of system time, idle time, and uaer time are meaaunzd for theae applicationa.Resulta are presented for an Intel Pamgon distributed-memory measagepassing multicomputer and compared to a Sun SPARCcenter 1 OOOE symmetric multiprocessor.

We propose three synchronous parallel algorithms for scalable parallel test set partitioned fault simulation. The algorithms are based on a new two-stage approach to parallelizing fault simulation for sequential VLSI circuits in which the test set is partitioned among the available processors, The test set partitioning inherent in the algorithms overcomes the good circuit logic simulation bottleneck that exists in traditional fault partitioned approaches to parallel fault simulation. The implementations were done on a shared memory multiprocessor and on a network of workstations. Two of the algorithms show a small degree of pessimism in a few cases, with respect to the fault coverage as compared with a uniprocessor run, while the third algorithm provides the same results as in a uniprocessor run. All algorithms provide excellent speedups and perform much better than a traditional fault partitioned approach, on both shared and distributed memory parallel platforms.

Simulated annealing, a methodology for solving combinatorial optimization problems, is a very computationally expensive algorithm and, as such, numerous researchers have undertaken efforts to parallelize it. In this paper, we investigate three of these parallel simulated annealing strategies when applied to standard cell placement, specifically the TimberWolfSC placement tool. We have examined a parallel moves strategy, as well as two new approaches to parallel cell placement-multiple Markov chains and speculative computation. These algorithms have been implemented in ProperPLACE, our parallel cell placement application, as part of the ProperCAD II project. We have constructed ProperPLACE so that it is portable across a wide range of parallel architectures. Our parallel moves algorithm uses novel approaches to dynamic message sizing, message prioritization, and error control. We show that parallel moves and multiple Markov chains are effective approaches to parallel simulated annealing when applied to TimberWolfSC, yet speculative computation is wholly inadequate.

Parallel algorithms developed for CAD problems today suffer from two important drawbacks. First, they are machine specific, and tend to perform poorly on architectures other than the one for they were designed. Second, the quality of results degrades significantly during parallel execution. In this paper, we address these two problems for an important CAD application: test generation for sequential circuits, We have developed a new parallel test generator, ProperTEST, that is portable across a range of MIMD parallel architectures. This work is part of the ProperCAD project which aims to develop CAD algorithms that run unchanged on shared and nonshared memory machines. We present performance data for ProperTEST on ISCAS 89 sequential circuits on a Sequent Symmetry, an Intel i860 hypercube, an NCUBE/2 hypercube, a network of Sun workstations, and an Encore Multimax. Parallel processing can also be used to improve on the fault coverage possible on one processor in a given amount of time. This was not possible in earlier approaches due to search anomalies. Using ProperTEST, we provide results on ISCAS 89 benchmark programs demonstrating the improvements in fault coverage as the number of processors is increased.

Distributed Memory Multicomputers (DMMs), such as the IBM SP-2, the Intel Paragon, and the Thinking Machines CM-5, offer significant advantages over shared memory multiprocessors in terms of cost and scalability. Unfortunately, the utilization of all the available computational power in these machines involves a tremendous programming effort on the part of users, which creates a need for sophisticated compiler and run-time support for distributed memory machines. In this paper, we explore a new compiler optimization for regular scientific applications-the simultaneous exploitation of task and data parallelism. Our optimization is implemented as part of the PARADIGM HPF compiler framework we have developed. The intuitive idea behind the optimization is the use of task parallelism to control the degree of data parallelism of individual tasks. The reason this provides increased performance is that data parallelism provides diminishing returns as the number of processors used is increased. By controlling the number of processors used for each data parallel task in an application and by concurrently executing these tasks, we make program execution more efficient and, therefore, faster.

In this paper we present some novel algorithms for scheduling hierarchical signal flow graphs in the domain of high-level synthesis. There are several key contributions of this paper. First, we develop a novel extension of the force directed scheduling problem which naturally handles loops and conditionals by coming up with a scheme of scheduling hierarchical signal flow graphs. Second, we develop three new parallel algorithms for the scheduling problem. Third, our parallel algorithms are portable across a wide range of parallel platforms. We report results on a set of high-level synthesis benchmarks on 8-processor SGI Challenge and a network of 4 SUN SPARCstation5 work stations. Finally, while some parallel algorithms for VLSI CAD reported by earlier researchers have reported a loss of qualities of results, our parallel algorithms produce exactly the same results as the sequential algorithms on which they are based.

Article Compiler support for hybrid irregular accesses on multicomputers Share on Authors: Antonio Lain Hewlett Packard Avda. Graells 501, 08190 S. Cugat del Valles, Barcelona-Spain Hewlett Packard Avda. Graells 501, 08190 S. Cugat del Valles, Barcelona-SpainView Profile , Prithviraj Banerjee University of Illinois, 1308 West Main Street, Urbana, IL University of Illinois, 1308 West Main Street, Urbana, ILView Profile Authors Info & Claims ICS '96: Proceedings of the 10th international conference on SupercomputingJanuary 1996 Pages 1–9https://doi.org/10.1145/237578.237579Online:01 January 1996Publication History 2citation177DownloadsMetricsTotal Citations2Total Downloads177Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Algorithm based techniques are based on checking for the preservation of certain properties possessed by global data following a set of computations. This often involves the introduction of a check variable which is updated in such a manner that, in the absence of roundoff errors, it equals the value of some function which involves all the data elements participating in the algorithm. However, roundoff errors accumulate in different ways in the updates involving the check variables and the computations involving data elements; this makes it highly unlikely that the equality is preserved exactly for an implementation of the algorithm on a real computer. Thus, the check step involves verifying the preservation of the equality to within a tolerance value. We propose a method for determination of the tolerance based on error analysis techniques. We present results on three numerical algorithms which show the effectiveness of our approach for data sets of varying sizes and data ranges.

This paper presents a model which can be used to characterize the diagnosability of Algorithm-Based Fault Tolerant (ABFT) systems. In the model, the relationship between processors computing useful data, the output data, and the check processors is defined in terms of matrix entries. Necessary and sufficient conditions for detecting and locating faults in the processors are derived, and based on them, efficient algorithms to evaluate the fault detection and location capabilities of the system are developed.

Algorithm-based fault-tolerance (ABFT) is an inexpensive method of incorporating fault-tolerance into existing applications. Applications are modified to operate on encoded data and produce encoded results which may then be checked for correctness. An attractive feature of the scheme is that it requires little or no modification to the underlying hardware or system software. Previous algorithm-based methods for developing reliable versions of numerical programs for general-purpose multicomputers have mostly concerned themselves with error detection. A truly fault-tolerant algorithm, however, needs to locate errors and recover from them once they are located. In a parallel processing environment, this corresponds to locating the faulty processors and recovering the data corrupted by the faulty processors. In this paper, we first present a general scheme for performing fault-location and recovery under the ABFT framework. Our fault model assumes that a faulty processor can corrupt all the data it possesses. The fault-location scheme is an application of system-level diagnosis theory to the ABFT framework, while the fault-recovery scheme uses ideas from coding theory to maintain redundant data and uses this to recover corrupted data in the event of processor failures. Results are presented on implementations of three numerical algorithms on a 16-processor Intel iPSC/2 hypercube multicomputer, which demonstrate acceptably low overheads for the single and double fault location and recovery cases.

Algorithm-based fault tolerance is an inexpensive method of achieving fault tolerance without requiring any hardware modifications. For numerical applications involving the iterative solution of linear systems arising from discretization of various PDEs, there exist almost no fault-tolerant algorithms in the literature. We describe an error-detecting version of a parallel algorithm for iteratively solving the Laplace equation over a rectangular grid. This error-detecting algorithm is based on the popular successive overrelaxation scheme with red-black ordering. We use the Laplace equation merely as a vehicle for discussion; we show how to modify the algorithm to devise error-detecting iterative schemes for solving linear systems arising from discretizations of other PDEs, such as the Poisson equation and a variant of the Laplace equation with a mixed derivative term. We also discuss a modification of the basic scheme to handle situations where the underlying solution domain is not rectangular. We then discuss a somewhat different error-detecting algorithm for iterative solution of PDEs which can be expected to yield better error coverage. We also present a new way of dealing with the roundoff errors which complicate the check phase of algorithm-based schemes. Our approach is based on error analysis incorporating some simplifications and gives high fault coverage and no false alarms for a large variety of data sets. We report experimental results on the error coverage and performance overhead of our algorithm-based error-detection schemes on an Intel iPSC/2 hypercube multiprocessor.

Fault simulation for sequential circuits numbers among the highly compute intensive tasks in the integrated circuit design process. In the quest for rapid design turn around, parallelization has been proposed to speed fault simulation. We introduce ProperPROOFS, a parallel extension of the PROOFS fault simulation package. ProperPROOFS exploits parallelism based on fault partitioning, incorporating static and dynamic partitioning schemes and a new asynchronous and distributed method of fault redistribution. We present results for circuits in the ISCAS-89 benchmark set across several parallel architectures. A detailed evaluation of results provides new insight into the use of fault partitioning to parallelize high performance serial fault simulation applications.

The PARADIGM compiler project provides an automated means to parallelize programs, written in a serial programming model, for efficient execution on distributed-memory multicomputers.A previous implementation of the compiler based on the PTD representation allowed symbolic array sizes, affine loop bounds and array subscripts, and variable number of processors, provided that arrays were singleor multi-dimensionally block distributed.The techniques presented here extend the compiler to also accept multidimensional cyclic and block-c yclic distributions within a uniform symbolic framework.These extensions demand more sophisticated symbolic manipulation capabilities.A novel aspect of our approach is to meet this demand by interfacing PARADIGM with a powerful off-the-shelf symbolic package, MathematicaTM.This paper describes some of the MathematzcaTM routines that performs various transformations, shows how they are invoked and used by the compiler to overcome the new challenges, and presents experimental results for code involving cyclic and block-cyclic arrays as evidence of the feasibility of the approach.1

Recent studies show that a stuck-at test applied at the operational speed of the circuit identifies more defective chips than a test having the same fault coverage but applied at a lower speed. Design-for-testability approaches based on full scan, partial scan, or silicon-based solutions such as CrossCheck achieve very high stuck-at fault coverage. However, in all these cases, the tests have to be applied at speeds lower than the operation speed. In this work, we investigate various design-for-testability (DFT) techniques for sequential circuits that permit at-speed application of tests while providing for very high fault coverage. The method involves parallel loading of flip-flops in test mode for enhanced controllability combined with probe point insertion for enhanced observability. Fault coverage and ATG effectiveness improved to greater than 96% and 99.7%, respectively, for the ISCAS89 sequential benchmark circuits studied when these nonscan DFT techniques were used. The average area overhead for the nonscan DFT enhancements was 9.9% for standard cell implementations of three circuits synthesized from high-level descriptions, compared to 20.2% for full scan. ATG effectiveness improved to greater than 99.3% for all three circuits with the nonscan DFT enhancements.>

Automatic test pattern generation (ATPG) for sequential circuits remains one of the most compute-intensive tasks in the integrated circuit design process. Although numerous attempts have been made to speed the ATPG process via parallelization, these attempts have often proved disappointing when compared against the best available serial algorithms using metrics of resultant quality and performance. In this paper we introduce ProperHITEC, a parallel extension of the HITEC/PROOFS sequential test generation package. ProperHITEC embodies a new approach to parallel ATPG; it is incrementally derived from one of the best-performing serial algorithms and this incremental derivation is implemented via the mechanisms of object-oriented programming. Results of running ProperHITEC on three parallel architectures, the Sun 4/600MP, the INTEL iPSC/860, and the Encore Multimax are presented. These results show that ProperHITEC achieves results virtually identical in quality to HITEC while achieving significant multiprocessor utilization.

In this paper, we present a partitioning approach of parallel logic synthesis, which is different from the previous approaches which involved parallelization of individual operations within the synthesis algorithm. We partition the given logic circuits and distribute the partitions to different processors for synthesis. For good load balancing, partitioning algorithm is tuned so that the estimated synthesis times of individual partitions are equal. To improve the quality of synthesized circuits, we propose a novel iterative repartitioning and resynthesis approach to parallel logic synthesis. Experimental evaluation in several large circuits are shown on a network of workstations, and results are compared with MIS.

The PARADIGM (PARAllelizing compiler for DIstributed-memory General-purpose Multicomputers) project at the University of Illinois provides a fully automated means to parallelize programs, written in a serial programming model, for execution on distributed-memory multicomputers. To provide efficient execution, PARADIGM automatically performs various optimizations to reduce the overhead and idle time caused by interprocessor communication. Optimizations studied in this paper include message coalescing, message vectorization, message aggregation, and coarse gram pipelining. To separate the optimization algorithms from machine-specific details, parameterized models are used to estimate communication and computation costs for a given machine. The models are also used in coarse gram pipelining to automatically select a task granularity that balances the available parallelism with the costs of communication. To determine the applicability of the optimizations on different machines, we analyzed their performance on an Intel iPSC/860, an Intel iPSC/2, and a Thinking Machines CM-5.

Compilers have focused on the exploitation of one of functional or data parallelism in the past. The PARADIGM compiler project at the University of Illinois is among the first to incorporate techniques for simultaneous exploitation of both. The work in this paper describes the techniques used in the PARADIGM compiler and analyzes the optimality of these techniques. It is the first of its kind to use realistic cost models and includes data transfer costs which all previous researchers have neglected. Preliminary results on the CM-5 show the efficacy of our methods and the significant advantages of using functional and data parallelism together for execution of real applications.

There are many applications in CFD and structural analysis that can be more accurately modeled using unstructured grids. Parallelization of implicit methods for unstructured grids is a difficult and important problem. This paper deals with coloring techniques to overlap computation and communication during the solution of implicit methods on message passing distributed memory multicomputers. An evaluation of coloring techniques for partitioned unstructured grids is first presented. Results show the importance of using partitioning information during coloring. It is next shown that overlapping computation and communication can be formalized as a generalized coloring problem. Modified coloring algorithms are used for this purpose. The PARTI library has been extended to support non-blocking gather-scatter operations and used in conjunction with these algorithms. Practicality issues are evaluated with experimental results on an Intel Paragon multicomputer.

The use of parallel platforms, despite their increasing availability, remains largely restricted to well-structured, numeric applications. We address the issue of facilitating the use of parallel platforms on unstructured problems through object-oriented design techniques and the actor model of concurrent computation. We present a multi-level approach to expressing parallelism for unstructured applications: a high-level interface based on the actor model of concurrent object-oriented programming and a low-level interface which provides an object-oriented interface to system services across a wide range of parallel architectures. The high- and low-level interfaces are implemented as part of the ProperCAD II C++ class library which supports shared memory, message-passing, and and hybrid architectures. We demonstrate our approach through a detailed examination of the parallelization process for an existing unstructured serial application, viz. a state-of-the-art VLSI computer-aided design application. We compare and contrast the library-based actor approach to other method for expressing parallelism in C++ on a number of applications and kernels.>

This paper discusses the design of two reconfiguration strategies for distributed memory multicomputer architectures under failures. The specific architectures to which we apply the techniques are hypercubes and meshes. The first scheme uses spare processors attached to certain processors in the hypercube or mash using a novel embedding technique. The second approach places spare processors along specific links in the hypercube or mesh. Both schemes involve the mapping of logical links of a virtual machine onto a set of physical links in the final reconfigured machine and hence suffer some performance degradation. We characterize the performance degradation through trace-driven simulation of real applications running on the faulty and reconfigured system. We find that the schemes have high reliability, suffer little degradation in performance, and are very low in cost.>

Combinational logic synthesis is a very important phase of VLSI system design. But the logic synthesis process requires large computing times if near optimal quality of the logic network is desired. Parallel processing is fast becoming an attractive solution to reduce the computational time. Recently, researchers have started to investigate parallel algorithms for problems in logic synthesis and verification. Much of the work in parallel algorithms for CAD reported to date, however, suffers from a major limitation. The parallel algorithms proposed for the CAD applications are designed with a specific underlying parallel architecture in mind. Moreover, incompatibilities in programming environments also make it difficult to port these programs across different parallel machines. As a result, a parallel algorithm needs to be developed afresh for every target parallel architecture. The ongoing project of ProperCAD offers an attractive solution to that problem. It allows the development and implementation of a parallel algorithm on the CHARM runtime system such that it can be executed in all the parallel machines without any change in the program. In this paper, we describe a portable parallel algorithm for logic synthesis based on the Transduction method, called ProperSYN. This algorithm uses an asynchronous message driven data-flow model of computation, with no explicit synchronizing barriers separating different phases of parallel computation as used in many previously developed parallel algorithms. Our algorithm is therefore more scalable to large numbers of processors. The algorithm has been implemented and it runs on a variety of parallel machines. We present results on several benchmark circuits for shared memory MIMD machines like Sequent Symmetry and Encore Multimax, distributed memory MIMD machine like the Intel/860 hypercube and distributed processing systems like networks of SUN workstations.>

Most parallel algorithms for VLSI CAD proposed to date work efficiently only on machines that they were designed for. As a result, these algorithms are dependent on the architecture for which they are developed and do not port easily to other parallel architectures. In an effort to address this problem, we are developing a Portable object-oriented parallel environment for CAD algorithms (ProperCAD). The objectives of this research are two-fold: 1) To develop new parallel algorithms that run in a portable object-oriented environment. We accomplish this in two stages. First, we develop CAD algorithms using a general purpose platform for portable parallel programming called CHARM developed at the University of Illinois. Concurrently, we are developing a C++ environment that is truly object-oriented and specialized for CAD applications; and 2) To design the parallel algorithms around a good sequential algorithm with a well-defined parallel-sequential interface. This will permit the parallel algorithm to benefit from future developments in sequential algorithms. This approach is described using one CAD application that has been implemented as part of this project-ProperEXT: a flat extractor for VLSI circuits. The algorithm, its implementation, and performance of ProperEXT on a range of parallel machines is presented. The implementation is portable across a variety of parallel platforms without change. It currently runs on an Encore Multimax, a Sequent Symmetry, Inter iPSC/2 and i860 hypercubes, a NCUBE 2 hypercube and a network of Sun Sparc workstations.>

Conventional logic synthesis systems are targeted towards reducing the area required by a logic block, as measured by the literal count or gate count; or, improving the performance in terms of gate delays; or, improving the testability of the synthesized circuit, as measured by the irredundancy of the resultant circuit. In this paper, we address the problem of developing reliability driven logic synthesis algorithms for multilevel logic circuits, which are integrated within the MIS synthesis system. Our procedures are based on concurrent error detection techniques that have been proposed in the past for two level circuits, and adapting those techniques to multilevel logic synthesis algorithms. Three schemes for concurrent error detection in a multilevel circuit are proposed in this paper, using which all the single stuck at faults in the circuit can be detected concurrently. The first scheme uses duplication of a given multilevel circuit with the addition of a totally self-checking comparator. The second scheme proposes a procedure to generate the multilevel circuit from a two level representation under some constraint such that, the Berger code of the output vector can be used to detect any single fault inside the circuit, except at the inputs. A constrained technology mapping procedure is also presented in this paper. The third scheme is based on parity codes on the outputs. The outputs are partitioned using a novel partitioning algorithm, and each partition is implemented using a multilevel circuit. Some additional parity coded outputs are generated. In all three schemes, all the necessary checkers are generated automatically and the whole circuit is placed and routed using the Timberwolf layout package. The area overheads for several benchmark examples are reported in this paper. The entire procedure is integrated into a new system called RSYN.>

Article Free Access Share on Non-scan design-for-testability techniques for sequential circuits Authors: Vivek Chickermane View Profile , Elizabeth M. Rudnick View Profile , Prithviraj Banerjee View Profile , Janak H. Patel View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993 Pages 236–241https://doi.org/10.1145/157485.164686Published:01 July 1993Publication History 49citation329DownloadsMetricsTotal Citations49Total Downloads329Last 12 Months43Last 6 weeks19 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

Numerous redundant disk organizations have been proposed and used to provide increased performance and reliability from the I/O subsystems architecture, and once a disk fails in such a system, different forms of spar ing and reconstruction have also been proposed. In this paper, we offer a comprehensive evaluation of the relation ship between various disk array architectures, various disk reconstruction strategies, and their reliability under various failure rate and repair rate distributions. Specifically, we perform the evaluations of the reliabilities (through a mea sure of system mean time to failure) of different redundant disk organizations with variations in each of the following orthogonal directions. We also consider the effect of the reconstruction strategy on the reliability. A third and im portant dimension to our study involves the use of realistic failure rates and repair rates of disks that are dependent on the workload and the organization of the disks. Finally, we perform our study of scalability of the results to varying sys tem sizes, by specifically addressing disk organizations with 16 to 10&4 disks. The paper's contribution is in presenting a uniform framework for evaluation of these multidimen sional studies, as well as offering an improved model for predicting disk array reliability taking into account system load as well as disk organization.

Functional or Control parallelism is an efiectiuc way to increase speedups in Multicomputers. Programs for these machines are represented by Macro Dataflow Graphs (MRGsJ for the purpose of functional parallelism analysk and exploitation. Algorithms for allocation and schedttlang of MDGs have been discussed along with some analysis of their optirnality. These algorithms attempt to minimize the execution time of any given MDG through exploitation of functional parallelism. Our preliminary results show their eflectiveness over naive algorithms.

Algorithm based fault tolerance is an inexpensive method of achieving fault tolerance without requiring any hardware modifications. Algorithm-based schemes have been proposed for a wide variety of numerical applications. However, for a particular class of numerical applications, namely those involving the iterative solution of linear systems, there exist almost no fault-tolerant algorithms in the literature. In this paper, we describe a fault-tolerant version of a parallel algorithm for iteratively solving the Laplace equation over a grid.

Distributed-memory multicomputers such as Intel iPSC/860, the NCUBE/2. The Intel Paragon and Connection Machine CM-5 offers significant advantages over shared-memory multiprocessors in terms of costs and scalability.

One of the most challenging steps in developing a parallel program for a distributed memory machine is determining how data should be distributed across processors. Most of the compilers being developed to make it easier to program such machines still provide no assistance to the programmer in this difficult and machine-dependent task. We have developed PARADIGM, a compiler that makes data partitioning decisions for Fortran 77 procedures. A significant feature of the design of PARADIGM is the decomposition of the data partitioning problem into a number of sub-problems, each dealing with a different distribution parameter for all the arrays. This paper presents the algorithms that, in conjunction with the computational and the communication cost estimators developed by us, determine those distribution parameters. We also present results obtained on Fortran procedures taken from the Linpack and Eispack libraries, and the Perfect Benchmarks. We believe these are the first results demonstrating the success of automatic data partitioning on a significant class of Fortran procedures.

A wide variety of fault tolerance techniques for VLSI technology are examined. Device-, gate-, and function-levels fault models are described. The basic methods available to the designer of fault tolerance measures are introduced by surveying redundancy techniques. Techniques of fault detection that use space, time, and information redundancies, algorithm-based fault tolerance, in VLSI components, large-scale processor-level implementations of fault detection, fault tolerance in automated VLSI production systems are discussed. Reconfiguration of the system and recovery of system operation are described. Issues relating to the reconfiguration after discovery of a fault in fabrication or in operation are discussed. Recovery capabilities of a VLSI microprocessor are reviewed.>

Two approaches to handling the computational requirements of computer-aided design problems are considered. One approach is to take advantage of the hierarchical nature of circuit design and develop hierarchical CAD algorithms. Another involves the use of parallel processing and development of parallel CAD algorithms. How these two approaches can be combined to speed up various CAD applications is discussed. Toward this goal, two general problems in scheduling are solved: parallelizable independent task scheduling (PITS) and parallelizable dependent task scheduling (PDTS). The PITS scheduling theory is applied to a parallel hierarchical circuit extractor, and the PDTS scheduling theory is applied to a parallel hierarchical global router. Both implementations show speedups of about six on eight processors of a shared-memory multiprocessor.>

The authors propose a heuristic procedure for partitioning a circuit into several blocks so that after the resynthesis of each block and subsequent reconnection there is a near-minimal number of redundant faults in the circuit. A probabilistic technique is used to estimate the size of a don't care set, and the partitioning approach tries to reduce the don't care size across the partitions. The approach, called PREST (for Partitioning and RESynthesis for Testability), has been applied on various MCNC and ISCAS benchmark circuits, and excellent results in terms of the size and testability of the synthesized circuit have been obtained.>

An algorithm based on the transduction method and implemented in the ProperCAD environment is described. The parallel ProperSYN algorithm attempts to make the execution time manageably small. The algorithm uses an asynchronous message driven computing model with no synchronizing barriers, and hence it is scalable to a larger number of processors. Also, the algorithm is portable across a wide variety parallel machines. Experimental results on various parallel machines are presented. The algorithm is built around a well-defined sequential algorithm interface such that there can be benefits from future expansion of the sequential algorithm.>

A parallel test generation algorithm, ProperTEST, for sequential circuits that is portable across a range of MIMD parallel architectures is discussed. It uses prioritized execution to ensure consistent speedups as the number of processors is increased. This consistency is achieved without loss of fault coverage with increase in the number of processors. This also permits the use of parallel processing to improve the fault coverage when the execution time is bounded. Results on ISCAS 89 benchmark programs are provided on a shared memory machine, a message passing machine, and a network of workstations. ProperTEST was run unchanged on these different architectures.>

A portable object-oriented parallel environment for CAD algorithms (ProperCAD) is described. The objectives of this research are twofold: to develop parallel algorithms that are portable and to design the parallel algorithms around a good sequential algorithm with a well-defined parallel-sequential interface, permitting the parallel algorithm to benefit from future developments in sequential algorithms. The first is achieved by writing the algorithms using the ProperCAD environment, a library of functions that permits portability of parallel CAD algorithms across MIMD machines. Programs written using this environment run unchanged on all parallel machines for which this environment is available.>

Freeing the user from the tedious task of generating explicit communication is one of the primary goals of numerous research projects on compilers for distributed memory machines. In the process of synthesis of communication, the effective use of collective communication routines offers a considerable scope for improving the program performance. This paper presents a methodology for determining the collective communication primitives that should be used for implementing the data movement at various points in the program. We introduce the notion of certain synchronous properties between array references in statements inside loops, and present tests to determine the presence of these properties. These tests enable the compiler to analyze quite precisely the communication requirements of those statements, and implement communication using appropriate primitives. These results not only lay down a framework for synthesis of communication on multicomputers, they also form the basis of our implementation of a system that statically estimates the communication costs of programs on multicomputers.

The authors deal with reconfiguration of a rectangular array of processors arranged as an N*N mesh, and a complete binary tree of N processors. They present new reconfiguration techniques that are modifications of the Diogenes approach proposed earlier by A.L. Rosenberg et al. (1983). These techniques reduce the overheads incurred in the earlier Diogenes schemes. Some of the previous approaches to the problem are summarized. Two schemes are presented for reconfiguring rectangular arrays and a scheme for reconfiguring trees. For the analysis of the different schemes presented, it is assumed that a processor has a square layout. These schemes are analyzed and their performance results are presented.>

Parallel algorithms for the geometric connected component labeling (GCCL) problem on a hypercube multiprocessor can be designed by dividing the domain, consisting of a number of rectangles, into regions using a slice or rectangular partitioning scheme. Each processor in the hypercube is assigned one partition. The processor determines the connected sets of rectangles in its partition. The connected sets at different processors have to then be combined across processors into globally connected sets. This merging problem is defined as the GCCL problem. Different algorithms for the GCCL problem are presented. Each of the algorithms involves d stages of message passing, for a d-dimensional hypercube. The basic idea in these algorithms is that in each stage a processor increases its knowledge of the domain. The algorithms described in this paper differ in their run time, memory requirements, and message complexity. These algorithms have been implemented on an Intel iPSC2/D4/MX hypercube.>

An approach to the problem of automatic data partitioning is introduced. The notion of constraints on data distribution is presented, and it is shown how, based on performance considerations, a compiler identifies constraints to be imposed on the distribution of various data structures. These constraints are then combined by the compiler to obtain a complete and consistent picture of the data distribution scheme, one that offers good performance in terms of the overall execution time. Results of a study performed on Fortran programs taken from the Linpack and Eispack libraries and the Perfect Benchmarks to determine the applicability of the approach to real programs are presented. The results are very encouraging, and demonstrate the feasibility of automatic data partitioning for programs with regular computations that may be statically analyzed, which covers an extremely significant class of scientific application programs.>

The performance evaluation, workload characterization, and trace-driven simulation of a hypercube multicomputer running realistic workloads are presented. Eleven representative parallel applications were selected as benchmarks. Software monitoring techniques were then used to collect execution traces. Based on the measurement results, both the computation and communication behavior of these parallel programs were investigated. The various time interval distributions were modeled by statistical functions which were verified by a nonlinear regression technique using the empirical data. The temporal and spatial localities of message destinations were also studied. A model for the temporal locality of message length was introduced and used to analyze the communication traces. A trace-drive simulation environment, which uses the communication patterns of the parallel programs as inputs, was developed to study the behavior of the communication hardware under real workload. Simulation results on DMA and link utilizations are reported.>

Article Free Access Share on Parallel test generation for sequential circuits on general-purpose multiprocessors Authors: Srinivas Patil IBM Corporation P.O. Box 950, Poughkeepsie, NY IBM Corporation P.O. Box 950, Poughkeepsie, NYView Profile , Prithviraj Banerjee Center for Reliable and High-Performance Computing, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL Center for Reliable and High-Performance Computing, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, ILView Profile , Janak H. Patel Center for Reliable and High-Performance Computing, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL Center for Reliable and High-Performance Computing, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, ILView Profile Authors Info & Claims DAC '91: Proceedings of the 28th ACM/IEEE Design Automation ConferenceJune 1991 Pages 155–159https://doi.org/10.1145/127601.127651Published:01 June 1991Publication History 27citation177DownloadsMetricsTotal Citations27Total Downloads177Last 12 Months8Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Present design for testability techniques, in general, result in a large area overhead und perjormance clegruclation. An algorithm is presented which uses the layoul infornzation as well as the knowledge generated during the testgeneration process to select a set of observable lestpoints. These testpoints are implemented at the luyout level and suffer virtually no area and performance overhead. We have petjiormecl an experimentul evuluation of this technique where testpoints were inserted to sequentiul ISCAS-benchmarks and the fault coverage was obtained along with the urea and the performance overheads. The results show that our design for testubiliv method is cost effective and produces a high jault coverage for sequential circuits.

The authors propose parallel algorithms to speedup the VLSI circuit extraction task. Given a VLSI layout as input, the problem of circuit extraction consists of determining the circuit connectivity and estimating the various electrical parameters such as the resistances of lines, capacitances of nodes, and dimensions of devices. Circuit extraction is a computationally intensive problem. The basic approach used in the parallel algorithms is the partitioning of a circuit into small regions, assigning each region to a processor and having the processors cooperate in performing the extraction procedures. The authors present a number of partitioning strategies that could be used. The authors have implemented the parallel algorithms on an Intel iPSC2 hypercube and an Encore 510 multimax shared memory multiprocessor.>

The authors present a quantitative analysis of the simulated evolution (SE) technique based on a variety of parameters. The measurement results and their relevance to practical implementations are discussed. A mathematical formulation of the SE algorithm is introduced. The associated Markov chain model is thoroughly analyzed. It is shown that the algorithm will hit a global minimum with probability one. The theoretical analysis suggests some modifications to a previously published SE-based method that was applied to cell placement problems. In order to compensate for additional computation times required by the new technique, the authors also introduce a novel hierarchical placement method. It has inherent advantages over the flat method in both CPU time requirements and result quality. It is also shown how a windowing method can be used to significantly reduce computation times.>

Heuristics are proposed to partition faults for parallel test generation with minimization of both the overall run time and test length as an objective. For efficient utilization of available processors, the work load has to be balanced at all times. Since it is very difficult to predict how difficult it will be to generate a test for a particular fault, the authors propose a load balancing method which uses static partitioning initially and then uses dynamic allocation of work for processors which become idle. A theoretical model is presented to predict the performance of the parallel test generation/fault simulation process. Experimental results based on an implementation of the Intel IPSC/2 hypercube multiprocessor using the ISCAS combinational benchmark circuits are presented.>

A new parallel hierarchical algorithm for global routing (PHIGURE) is presented. The router is based on the work of M. Burstein and R. Pelavin, (IEEE Trans. CAD, vol.CAD-2, no.4, p.223-34, Oct. 1983) but has many extensions for general global routing and parallel execution. Main features of the algorithm include structured hierarchical decomposition into separate independent tasks which are suitable for parallel execution and adaptive simplex solution for adding feedthroughs and adjusting channel heights for row-based layout. The algorithm is described and results are presented for a shared-memory multiprocessor implementation. >

This paper presents a mathematical formulation of the Simulated Evolution algorithm, a novel optimization technique, followed by a thorough analysis of the associated Markovchain model. We show that the algorithm will reach a global minimum with probability one, and also introduce a novel hierarchical placement technique. Finally, we describe a Standard Cell placement program based on the new approach whose preliminary results are comparable to the best Simulated Annealing algorithms.

An algorithm is presented that combines the benefits of hierarchical analysis and parallelism. The input is a hierarchical description of the circuit. The authors formulate and solve a general problem in scheduling. The parallel algorithm for hierarchical circuit extraction has been implemented on an Encore shared memory multiprocessor.>

A novel switch-level simulator, called SNEL, is presented. The SNEL simulator preprocesses the circuit description to abstract its functionality prior to simulation. Functional abstraction is concisely defined in terms of the functional domain and the functional application of circuit constructs. SNEL uses four algorithms that operate on levels ranging from single circuit elements to multiple DC-connected components. Since the functional abstraction preserves the complete functionality of the circuit, the accuracy of the simulation is maintained. However, SNEL models the circuit at a higher and more abstract level, which increases its simulation speed. The presented algorithms were implemented and tested on commercial designs. Without functional abstraction, the simulation speed of SNEL is competitive with current simulators. When functional abstraction was used, the simulation speed increased by more than an order of magnitude.>

In switch-level simulation, nodes carry a charge on their parasitic capacitance from one evaluation to the next, which gives them a memory quality. A node is classified as temporary if its memory aspect is lost and cannot affect the circuit operation, whereas a node is classified as a memory node if the memory of the node is maintained and can affect the circuit operation. Accurate classification of nodes into temporary and memory nodes increases the performance of compiled simulators and high-level model generators. An approach for reliable automatic classification of nodes in a switch-level description is introduced. Both an exhaustive, exponential-time algorithm and a polynomial-time heuristic are presented. The heuristic was implemented and tested for several large circuits, including a commercial microprocessor. For this processor, the proposed heuristics identified an average of 92% of all nodes as temporary nodes. The heuristic was applied in a high-level model generator and significantly increased its performance.>

The I/O behavior of some scientific applications, a subset of Perfect benchmarks, executing on a multiprocessor is studied. The aim of this study is to explore the various patterns of I/O access of large scientific applications and to understand the impact of this observed behavior on the I/O subsystem architecture. I/O behavior of the program is characterized by the demands it imposes on the I/O subsystem. It is observed that implicit I/O or paging is not a major problem for the applications considered and the I/O problem is mainly manifest in the explicit I/O done in the program. Various characteristics of I/O accesses are studied and their impact on architecture design is discussed.

The authors present the architecture, methodology and performance evaluation of a message-passing coprocessor (MPC) which can accelerate message communication in a distributed memory multicomputer (i.e. iPSC/2 hypercube). The MPC is a microprogrammable processor which offloads from the CPU the burden of communication and speeds up the software processing by directly executing message passing instructions in microcode. It supports process scheduling, message buffer management, and fast buffer copying. The most unique feature of the MPC is that it performs software caching for expected message destinations and buffers. The MPC works closely with a virtual channel router which is a smart routing controller and supports virtual channels and cached circuits. The software and hardware overhead of communication can be reduced significantly by these two processors. The performance is confirmed by trace-driven simulation.>

The task of synthesizing algorithm-based checking techniques for general applications is investigated. The problem is approached at the compiler level by identifying linear transformations in Fortran DO loops and restructuring program statements to convert nonlinear transformations to linear ones. System-level checks based on this property are proposed. The approach is demonstrated with example problems of matrix multiplication and the LINPACK routine: DGEFA.>

The design of fault-tolerant hypercube multiprocessor architecture is discussed. The authors propose the detection and location of faulty processors concurrently with the actual execution of parallel applications on the hypercube using a novel scheme of algorithm-based error detection. System-level error detection mechanisms have been implemented for three parallel applications on a 16-processor Intel iPSC hypercube multiprocessor: matrix multiplication, Gaussian elimination, and fast Fourier transform. Schemes for other applications are under development. Extensive studies have been done of error coverage of the system-level error detection schemes in the presence of finite-precision arithmetic, which affects the system-level encodings. Two reconfiguration schemes are proposed that allow the authors to isolate and replace faulty processors with spare processors.>

The increasing demands for high-performance signal processing along with the availability of inexpensive high-performance processors have results in numerous proposals for special-purpose array processors for signal processing applications. A functional-level concurrent error-detection scheme is presented for such VLSI signal processing architectures as those proposed for the FFT and QR factorization. Some basic properties involved in such computations are used to check the correctness of the computed output values. This fault-detection scheme is shown to be applicable to a class of problems rather than a particular problem, unlike the earlier algorithm-based error-detection techniques. The effects of roundoff/truncation errors due to finite-precision arithmetic are evaluated. It is shown that the error coverage is high with large word sizes.>

For circuits of VLSI complexity, test generation time can be prohibitive. Most of the time is consumed by hard-to-detect (HTD) faults, which might remain undetected even after a large number of backtracks. The problems inherent in a uniprocessor implementation of a test generation algorithm are identified, and a parallel test generation method which tries to achieve a high fault coverage for HTD faults in a reasonable amount of time is proposed. A dynamic search space allocation strategy which allocates disjoint search spaces to minimize the redundant work is proposed. The search space allocation strategy tries to utilize the partial solutions generated by other processors to increase the probability of searching in a solution area. The parallel test generation algorithm has been implemented on an Intel iPSC/2 hypercube. It is shown that parallel processing of HTD faults does indeed result in high fault coverage, which is otherwise not achievable by a uniprocessor algorithm. The parallel algorithm exhibits superlinear speedups in some cases due to search anomalies.>

A discussion is presented of two ways of mapping the cells in a two-dimensional area of a chip onto processors in an n-dimensional hypercube such that both small and large cell moves can be applied. Two types of move are allowed: cell exchanges and cell displacements. The computation of the cost function in parallel among all the processors in the hypercube is described, along with a distributed data structure that needs to be stored in the hypercube to support such a parallel cost evaluation. A novel tree broadcasting strategy is presented for the hypercube that is used extensively in the algorithm for updating cell locations in the parallel environment. A dynamic parallel annealing schedule is proposed that estimates the errors due to interacting parallel moves and adapts the rate of synchronization automatically. Two novel approaches in controlling error in parallel algorithms are described: heuristic cell coloring and adaptive sequence control. The performance on an Intel iPSC-2/D4/MX hypercube is reported.>

Several issues concerning the design of an I/O (input/output) system for a multiprocessor such as a hypercube are examined. A methodology is proposed for connecting the I/O processors to such a system for efficient I/O access. The effect of I/O communication on the multiprocessor network is analyzed. Different disk organizations that can be employed within such a system are evaluated to see which organization has a better performance. It is observed that parallelism in serving an I/O request plays a dominant role in the scientific workload. The problem of mapping specific data structures such as matrices onto the disks so that the data can be accessed efficiently is considered.>

The authors provide an in-depth study of the various issues and tradeoffs available in algorithm-based error detection, as well as a general methodology for evaluating the schemes. They illustrate the approach on an extremely useful computation in the field of numerical linear algebra: QR factorization. They have implemented and investigated numerous ways of applying algorithm-based error detection using different system-level encoding strategies for QR factorization. Specifically, schemes based on the checksum and sum-of-squares (SOS) encoding techniques have been developed. The results of studies performed on a 16-processor Intel iPSC-2/D4/MX hypercube multiprocessor are reported. It is shown that, in general, the SOS approach gives much better coverage (85-100%) for QR factorization while maintaining low overheads (below 10%).>

For circuits of VLSI complexity, test generation time can be prohibitive. Most of the time is consumed by hard-to-detect (HTD) faults which might remain undetected even after a large number of backtracks. We identify the problems inherent in a uniprocessor implementation of a test generation algorithm and propose a parallel test generation algorithm which tries to achieve a high fault coverage for HTD faults in a reasonable amount of time. A dynamic search space allocation strategy is used which ensures that the search spaces allocated to different processors are disjoint. The parallel test generation algorithm has been implemented on an Intel iPSC/2 hypercube. Results are presented using the ISCAS combinational benchmark circuits which conclusively prove that parallel processing of HTD faults does indeed result in high fault coverage which is otherwise not achievable by a uniprocessor algorithm in limited CPU time. The parallel algorithm exhibits superlinear speedups in some cases due to search anomalies.

A new row-based parallel algorithm for standard-cell placement targeted for execution on a hypercube multiprocessor is presented. Key features of this implementation include a dynamic simulated-annealing schedule, row-partitioning of the VLSI chip image, and two novel approaches to control error in parallel cell-placement algorithms: (1) Heuristic Cell-Coloring; (2) Adaptive Sequence Length Control.

An algorithm, PACE2, is described which is targeted to the second phase of extraction, called the parameter extraction phase. The authors have interfaced two models for resistance and capacitance. They propose a different partitioning scheme, namely, by equal number of rectangles, so as to balance the load. The parallel algorithm has been implemented on the Intel iPSC2/D4-MX hypercube.>

An accurate timing model is presented for MOS circuits, which is based on a multiple-valued logic representation, accurate RC models for delay calculations derived from transistor characteristics and slope information, and accurate models for physical failures. A delay fault simulator (FACT) based on this model has been implemented. Results for various MOS circuits are described and compared with those for SPICE and RSIM.>

In this paper, we look at several issues concerning the design of a disk system for a multiprocessor such as a hypercube. We propose a methodology for connecting the I/O processors to such a system for efficient I/O access. An analysis is presented to see the effect of I/O communication on the network of the multiprocessor. We evaluate different disk organizations that can be employed within such a system to see which organization has a better performance. Then we consider the problem of mapping specific data structures such as matrices onto the disks such that the data can be accessed efficiently.

The authors address the issues involved in providing an integrated test generation/fault simulation environment on a parallel processor. They propose heuristics to partition faults for parallel test generation with minimization of the overall run time and test length as an objective. For efficient utilization of available processors, the work load has to be balanced at all times. Since it is very difficult to predict a priori how difficult it is to generate a test for a particular fault, the authors propose a load-balancing method which uses static partitioning initially and then dynamic allocation of work for processors which become idle. They present experimental results based on an implementation on the Intel iPSC/2 hypercube multiprocessor using the ISCAS combinational benchmark circuits. The main contribution of the work described is to show that if one is not careful in the design of a parallel algorithm, apart from inefficient utilization of available processors, degradation in the quality of solutions can occur.>

In many cases, it may be possible to redesign parallel algorithms so as to provide a low-cost online scheme for hardware error detection without any hardware modifications. This approach is called algorithm-based error detection. Two useful computations in signal processing are analyzed: QR factorization and singular-value decomposition. For each of these applications, numerous ways of applying algorithm-based error detection using different system-level encoding strategies are investigated. Different schemes have been observed to result in varying error coverages and time overheads. The results of studies performed on a 16-processor Intel iPSC-2/D4/MX hypercube multiprocessor are reported.>

General purpose parallel processing machines are increasingly being used to speed up a variety of VLSI CAD applications. This paper addresses logic simulation on parallel machines by exploiting the concurrency in the circuit being simulated (called data parallelism) as opposed to exploiting parallelism inherent in the simulation algorithm itself (called functional parallelism). The most crucial step in obtaining the maximum parallelism using data parallelism is the partitioning of circuit elements. We introduce a cost function which tries to model the simulation of a logic circuit in a parallel environment. The cost function tries to estimate the parallel run time for logic simulation given the processor assignment and the underlying multiprocessor architecture. We then present different heuristic algorithms to partition the circuit and evaluate the efficiency of these algorithms using the proposed cost function. Partitioning algorithms for both event-driven and compiled code simulation are given.

The combining multistage interconnection network uses 4*4 switches as switching elements and introduces an extra stage of such switches and links to create four independent paths between any source-destination pair. Four copies of every message are sent through the network simultaneously. The scheduling discipline, the design of the switching elements to support the discipline, and the theoretical proof of correctness of the design constitute the key contributions of this study. Estimates are provided of various network parameters as a function of the workload, using analytical models and detailed network simulations. It is shown that the proposed design for fault tolerance is more cost-effective than the brute-force technique of having multiple copies of the network.>

Alternative ways of configuring an I/O subsystem with multiple disks to improve the I/O performance are considered. Specifically, the author consider disk synchronization, data declustering/disk striping, and a combination of both these approaches. They evaluate many different organizations that have not been considered before. The effects of block size and other parameters of the system are examined. Two different workloads are considered for the evaluation: a file/transaction system workload and a scientific applications workload. Through simulations it is shown that synchronized organizations perform better than other organizations at very low request rates; that there is a tradeoff in the amount of declustering/synchronization to be used in a system; and that systems with higher parallelism in reading a file perform better in a scientific workload.>

ESP (evolution-based standard cell placement) is a program package designed to perform standard cell placement including macro-block placement capabilities. It uses the novel heuristic method of simulating an evolutionary process to minimize the cell interconnection wire length. While achieving comparable results to popular simulated annealing algorithms, ESP usually requires less CPU time. A concurrent version designed to run on a network of loosely coupled processors, such as workstations connected via Ethernet, has also been developed. For medium to large circuits (>250 cells per processor) concurrent ESP achieves linear speedup.>

Hypercube multiprocessors achieve a cost-effective and feasible approach to supercomputing by directly connecting a large number of low-cost processors with local memory, which cooperate on tasks by message-passing. An efficient parallel algorithm to speed up the VLSI circuit extraction task on a hypercube multiprocessor is proposed. The basic approach consists of partitioning of a circuit into smaller regions, assigning each region to a processor of the hypercube, and having the processors cooperate in performing the extraction procedures. The algorithm supports the use of different models for electrical parameter calculations of varying degrees of accuracy and computational complexity. The algorithm has been implemented in a program called PACE (parallel circuit extractor) on the Intel iPSC/D4-MX hypercube. Speedup results for the algorithm on many realistic VLSI circuits are presented.>

Reconfiguration strategies in VLSI processor arrays have been advocated in the recent literature as a means of achieving higher production yield and higher reliability. The authors present reconfiguration techniques for rectangular arrays that are generalizations of the Diogenes approach proposed earlier by A.L. Rosenberg (1983). These techniques overcome many of the limitations of the earlier Diogenes schemes. Two schemes for reconfiguring rectangular arrays are presented. The first scheme for reconfiguring an N*N rectangular array uses r additional rows and c additional columns. It guarantees reconfiguration as long there are at most c columns that have more than r faulty processors. The second scheme uses spare processors. It guarantees reconfiguration as long as there are enough spare processors, and in any window of N processors in a particular linearization there are at most k faulty processors, where k is a parameter of the design.>

The algorithm begins with an initial placement of nets in the channel using the number of tracks equal to the density of the channel. Overlapping subnets are permitted at this stage as the annealing process will gradually work to remove the overlaps. Transformations are then repeatedly applied to the channel state by moving nets around the channel in a parallel fashion. By allowing overlap situations and controlling them with appropriate cost function, the algorithm is capable of producing very good results with the advantage of decreased runtime from the parallelism. and can also be applied to extensions of the channel routing problem, such as switchbox routine with obstacle avoidance.>

The cube-connected cycles network is suitable for realization in VLSI, since it satisfies the properties of degree boundedness of the nodes (=3), and regularity of layout. Another network called the cubical ring-connected cycles (CRCC) is proposed that has all the desirable features of the cube-connected cycle (CCC) and is single-cycle fault tolerant as well. The degree of each processor is less than or equal to four, the number of processors increases from 2/sup r+s/ to 2/sup r/(2/sup 2/+1), for integers r and s, and the number of links increases by a factor of one-third over the corresponding CCC. Reliability improvements of the CRCC network over the CCC are studied. A regular layout scheme suitable for VLSI implementation of the CRCC is presented. Reconfiguration techniques under failures of processors in the CRCC are discussed.>

The problem of minimizing the number of service ports of a central facility which serves a number of users subject to some constraints is addressed. At any time, a set of at most s users may want to use the facility, and one user can be connected to each port at a given time. It is assumed that there are direct communication links from users to service ports, with at most d links incident at a single service port. This problem maps to the graph-theoretic problem of minimizing the number of outputs of a bipartite graph with n inputs, such the degree of each output node is at most d and every set of k>

In this paper, we present a parallel simulated annealing algorithm for standard cell placement that is targeted to run on the Intel Hypercube. We present a novel tree broadcasting strategy that is used extensively in our algorithm for updating cell locations in the parallel environment. Studies on the performance of our algorithm on example industrial circuits show that it is faster and gives better final placement results than the uniprocessor simulated annealing algorithms.

ESP (Evolution-based Standard cell Placement) is a new program package designed to perform standard cell placement and includes macro-block placement capabilities. It uses the new heuristic method of simulating an evolutionary process in order to minimize the cell interconnection wire length. While achieving results comparable to or better than the popular Simulated Annealing algorithm, ESP performs its task about ten times faster.

A fault-secure dictionary machine is presented in this paper. The symmetry of the binary tree architecture for a dictionary machine is exploited to obtain fault-secureness with little overhead. The proposed design utilizes only one extra processor and with some other modifications to the structure of the processors, can detect a single failure of a processor or a link. The proposed design keeps two copies of each record and whenever a record is extracted from the machine the two copies are compared to detect if any fault has occurred. The low overhead is a result of observing the fact that at any given time all the processors of the machine need not be active and these potentially-idle processors are used to do redundant processing to enable detecting single faults.

An important consideration in the design of high- performance multiple processor systems should be in ensuring the correctness of results computed by such complex systems which are extremely prone to transient and intermittent failures. The detection and location of faults and errors concurrently with normal system operation can be achieved through the application of appropriate on-line checks on the results of the computations. This is the domain of algorithm-based fault tolerance, which deals with low-cost system-level fault-tolerance techniques to produce reliable computations in multiple processor systems, by tailoring the fault-tolerance techniques toward specific algorithms. This paper presents a graph-theoretic model for determining upper and lower bounds on the number of checks needed for achieving concurrent fault detection and location. The objective is to estimate ate the overhead in time and the number of processors required for such a scheme. Faults in processors, errors in the data, and checks on the data to detect and locate errors are represented as a tripartite graph. Bounds on the time and processor overhead are obtained by considering a series of subproblems. First, using some crude concepts for t-fault detection and t-fault location, bounds on the maximum size of the error patterns that can arise from such fault patterns are obtained. Using these results, bounds are derived on the number of checks required for error detection and location. Some numerical results are derived from a linear programming formulation.

This paper proposes a new logical model for nMOS and CMOS circuits. Existing gate-level and switch-level models are limited in their ability to simulate MOS circuit behavior accurately when modeling physical failures. The model proposed in this paper is in the form of a multivalued algebra defined on a set of node states. The state of a node is represented as a pairwhere "a" specifies the condition of a node and "b" specifies the logic level: There are five conditions and five logic levels. The assignment of node states is done dynamically during the process of logic simulation. The rules of the algebra are used to derive state tables that model the behavior of transistors. Our general model of a transistor allows for strong interactions between all three terminals of a transistor. This enables us to model the effects of physical failures such as a short between the gate and drain of a transistor. A simulation algorithm based on the algebra is discussed, and techniques for simulating physical failures in MOS circuits using the algebra are indicated.