This paper presents the first published industrial practice (to the best of our knowledge) to reuse high-level/C++ system simulation model through OSCI TLM 2.0 Library to verify its corresponding RTL implementation in FPGA. ESL verification methodology is employed in the design regression of EPC C1Gen2 RFID tag. Around 200 times speedup is observed using ESL over conventional RTL simulation in regression runs (after logic bug fixes). This clearly shows ESL verification is a successful candidate to reuse high-level test harness for IC functional verification, especially in today's increasingly complex IC design world. On top of the successful use of the ESL functional verification flow on the design, we also show the infrastructure to use SystemC Verification Library (SCV) for formal verification. The functional and formal verification combined is thus the proposed ESL verification methodology.

We present a tensor product formulation for Hilbert space-filling curves. Both recursive and iterative formulas are expressed. We view a Hilbert space-filling curve as a permutation which maps two-dimensional 2/sup n//spl times/2/sup n/ data elements stored in the row major or column major order to the order of traversing a Hilbert space-filling curve. The tensor product formula of Hilbert space-filling curves uses several permutation operations: stride permutation, radix-2 gray permutation, transposition, and antidiagonal transposition. The iterative tensor product formula can be manipulated to obtain the inverse Hilbert permutation. Also, the formulas are directly translated into computer programs which can be used in various applications including R-tree indexing, image processing, and process allocation, etc.

This paper presents tensor product formulas for modeling fault tolerant architectures and their corresponding reconfiguration algorithms. In our approaches, a network topology is first described with simple tensor product formulas, and then, by adding a set of permutation matrices and applying the direct sum operation, the reconfigurable architecture can be completely represented. Research results demonstrate three important facts: (1) by providing clarity and simplicity in mathematical form, tensor product representation is well-suited for the modeling of fault tolerant architectures; (2) with the tensor product model, traditional centralized reconfiguration processes can be transformed, in straightforward steps, to execute in a distributed manner; (3) furthermore, with the tensor product algebraic manipulations, complex architectures can be systematically and recursively constructed from simple basic blocks.

In this paper we use the tensor product notation as the framework of a programming methodology for designing various parallel prefix algorithms. In this methodology, we first express a computational problem in its matrix form. Next, we formulate a matrix equation for the matrix of the computational problem. Then, solve the matrix equation to obtain some simple matrices. Finally, we recursively factorize the subproblem to obtain a tensor product formula representing an algorithm for this problem. We will use the parallel prefix computation problem to illustrate our methodology and derive various parallel prefix algorithms including divide-and-conquer and recursive doubling algorithms.

This paper presents a design methodology for developing efficient distributed-memory parallel programs for block recursive algorithms such as the fast Fourier transform (FFT) and bitonic sort. This design methodology is specifically suited for most modern supercomputers having a distributed-memory architecture with a circuit-switched or wormhole routed mesh or a hypercube interconnection network. A mathematical framework based on the tensor product and other matrix operations is used for representing algorithms. Communication-efficient implementations with effectively overlapped computation and communication are achieved by manipulating the mathematical representation using the tensor product algebra. Performance results for FFT programs on the Intel Paragon are presented. © 1998 John Wiley & Sons, Ltd.

This paper presents a design methodology for developing efficient distributed-memory parallel programs for block-recursive algorithms such as the fast Fourier transform and bitonic sort. This design methodology is specifically suited for most modern supercomputers having a distributed-memory architecture with circuit-switched or wormhole routed mesh or hypercube interconnection network. A mathematical framework based on the tenser product and other matrix operations is used for representing algorithms. Communication-efficient implementations with effectively overlapped computation and communication are achieved by manipulating the mathematical representation using the tenser algebra. Performance results for FFT programs on the Intel iPSC/860 and Intel Paragon are presented.

We address the development of efficient methods for performing data redistribution of arrays on distributed-memory machines. Data redistribution is important for the distributed-memory implementation of data parallel languages such as High Performance Fortran. An algebraic representation of regular data distributions is used to develop an analytical model for evaluating the communication cost of data redistribution. Using this algebraic representation and the analytical model, an approach to communication-efficient data redistribution is developed. Implementation results on the Intel iPSC/860 are reported.

To minimize the amount of computation and storage for parallel sparse factorization, sparse matrices have to be reordered prior to factorization. We show that none of the popular ordering heuristics proposed before, namely, mulitple minimum degree and nested dissection, perform consistently well over a range of matrices arising in diverse application domains. Spectral partitioning has been previously proposed as a means of generating small vertex separators for nested dissection of sparse matrices, so that the resulting ordering is amenable to efficient distributed parallel factorization with good load balance and low inter-processor communication. We show that nested dissection using spectral partitioning performs well for matrices arising from finite-element discretizations, but results in excessive fill compared to the minimum degree ordering for unstructured matrices such as power matrices and those arising from circuit simulation. The relative effectiveness of these two ordering schemes for parallel factorization is shown to vary widely for matrices arising from different application domains. We present an ordering strategy that performs consistently well for all matrix types. Its ordering is comparable or better than either minimum degree or nested dissection for all matrices evaluated. Performance results on the Intel iPSC/860 are reported.

Presents EXTENT (EXpert system for TENsor product formula Translation) which is a programming environment for the automatic generation of parallel/vector programs from tensor product formulas. A tensor (Kronecker) product based programming methodology is used for designing high-performance programs on various architectures. In this programming methodology, block recursive algorithms such as the fast Fourier transform and Strassen's matrix multiplication algorithm are expressed as tensor product formulas involving tensor product and other matrix operations. A tensor product formula can be systematically translated into parallel and/or vector code for various parallel architectures. A prototype system which generates programs for the Cray Y-MP, Cray T3D and Intel Paragon has been developed. Performance results for some generated programs are presented.>

Many engineering applications use irregular array access functions. Compile-time characterization of the computation structure of such applications is infeasible, making the automatic generation of efficient communication dificuit. This paper considers the Inspector-Executor (IEJ compilalion model to handle such applications. In this model, a run-time inspection of the computation is followed by the aciual execution. This paper discusses the assue of automatic compile-time identification of sections of a program that have recurrent computational patterns so that the cost of run-time inspection is amortizable over many executions. An algorithm is presented and an illusiraitve example is given.

The concept of supernodes has been widely used in the design of algorithms for the solution of sparse linear systems of equations. This paper discusses the use of supernodes in the design of algorithms for sparse Cholesky factorization on distributed-memory multiprocessors. A new algorithm that is communication efficient, has good load balance, and benefits significantly from supernodes is presented.

Efficient generation of communication sets and local index sets is important for evaluation of array expressions in scientific languages such as Fortran-90 and High Performance Fortran implemented on distributed-memory machines. We show that for arrays affinely aligned with templates that are distributed on multiple processors with a block-cyclic distribution, the local memory access sequence and communication sets can be efficiently enumerated using closed forms. First, closed form solutions are presented for arrays that are aligned with identity template that are distributed using block or cyclic distributions.

We p~esent transposition a~gorithms fo?' matrices that do not fit in main memory.Transposition is interpreted m a permutation of the vector obtained by mapping a matriz to linear memoTy.A lgopithms am derived j%om factorization of this perm~tation, using a class of permutations related to the tensor prodwt.Using this formulation of transposition, we jirst obtain seveTal known aigo?'ithms and then we derive a new algorithm which Teduces the number of dish accesses TequiTed.The new algoTithm was compaTed to ezisting algorithms wing an implementation on the Intel iPSC/860.Thti comparison shows the benefits of the new aigoTithm.

The authors present an algebraic theory based on tensor products for modeling direct interconnection networks. This theory has been used for designing and implementing block recursive numerical algorithms on shared-memory vector multiprocessors. This theory can be used for mapping algorithms expressed in tensor product form onto distributed-memory architectures. The authors focus on the modeling of direct interconnection networks. Rings, n-dimensional meshes, and hypercubes are represented in tensor product form. Algorithm mapping using tensor product formulation is demonstrated by mapping matrix transposition and matrix multiplication onto different networks.>

The authors study the use of multilinear algebra in designing and implementing algorithms for linear computations. In particular, they discuss their experience in using these techniques on the Cray Y-MP and to implement Strassen's matrix multiplication algorithm on the Encore Multimax. It is concluded that the formulation of numerical algorithms in terms of the constructs of multilinear algebra, especially the tensor product, together with the coding methods presented, simplifies the writing of the programs for implementing these algorithms. By making the implementation process simpler and more mechanical, one can more easily experiment with and monitor the coding of these algorithms and thereby find better implementations.>

Our concern is the mechanical certification of transformations of sequential program executions into parallel executions with equivalent semantics. The objective of such transformations is to accelerate the execution of programs. The result reported here is a mechanically certified theorem of optimality. We present a transformation which applies to every program in a particular programming language, the language of sorting networks. This transformation transforms the sequential execution of any sorting network into an execution which is as fast or faster than any other transformation which applies to every sorting network. The theorem is stated formally in a mechanized logic.