Instruction systolic arrays for exact parallel linear algebraic computation

Abstract

This thesis develops new computational algorithms for parallel/distributed error-free (exact) rational (real and complex) computing and its applications to exact linear algebraic computing. The practical realization of these parallel algorithms in VLSI systems using a new concept known as Instruction Systolic Arrays (ISA) is considered. Thus, the thesis represents the author’s contribution to the theory, design, and implementation of parallel/distributed algorithms for exact rational/linear algebraic computing using ISA processors. This thesis consists of six chapters with the following contents.

CHAPTER 1 INSTRUCTION SYSTOLIC ARRAYS - A PROGRAMMABLE PARALLEL ARCHITECTURE Chapter 1 introduces the concept of Instruction Systolic arrays (ISA). The ISA is a new versatile programmable parallel architecture that retains all the advantages of systolic arrays. In the ISA, instructions and boolean selectors are pumped through the processing array. The ISA has tremendous potential for VLSI computing because of its ability to execute different types of programs on the same processing array. We also introduce a variant of the ISA known as the Single Instruction Systolic Array (SISA). In the SISA, single instructions and selectors are pumped through the processing array.

CHAPTER 2 INSTRUCTION SYSTOLIC ARRAYS FOR DISTRIBUTED CHINESE REMAINDERING/ INTERPOLATION ALGORITHMS We present a parallel/ distributed algorithm for a fundamental problem in Numerical Computing/algebraic computing, namely interpolation and the closely related Chinese remaindering. The ISA implementation of this algorithm is described. A generalization of the interpolation algorithm for multivariable is then presented. The multivariable interpolation algorithm can be realized in a ISA as well as in a pyramid architecture. The Occam simulation of a pyramid for multivariable interpolation is also described. We then present a parallel/ distributed algorithm for rational function interpolation and consider its ISA implementation.

CHAPTER 3 PARALLEL MATRIX COMPUTATION USING ISA This chapter introduces a parallel algorithm for the generalized inversion (g-inversion) of matrices, which involves parallel matrix addition and multiplication operations. The ISA implementation of this algorithm is described. The solution of a homogeneous system of linear algebraic equations is based on g-inverse computation and we indicate its ISA implementation. The solution of such equations has important practical applications in finding Petri net invariants, chemical equation balancing and dimensional analysis. Two other important g-inversion algorithms - one iterative and the other direct - are also described.

CHAPTER 4 PARALLEL ERROR-FREE RATIONAL ARITHMETIC - ISA IMPLEMENTATION This chapter introduces a new parallel error-free (exact) rational arithmetic system called Parallel Rational Hensel code arithmetic (Para-Hensel code or PHC). We introduce algorithms for parallel element-wise arithmetic operations, and for encoding and decoding PHC codes. We briefly indicate the ISA implementation of these algorithms. We also consider the application of PHC for exact parallel matrix g-inversion with systolic processors.

CHAPTER 5 PARALLEL COMPLEX RATIONAL AND MATRIX ARITHMETIC USING GAUSSIAN PRIME CODES In this chapter, we introduce a new parallel exact complex rational arithmetic system based on Gaussian prime codes. Two closely related methods for constructing these codes are described. The first method uses several distinct (multiple) Gaussian primes to construct Gauss-Hensel codes (GHC). The second method uses the powers of one or more Gaussian primes to construct Gauss p-adic codes (GPC). Their practical applications and extension to parallel inversion of complex matrices are described. These systems are amenable for massively parallel realization.

CHAPTER 6 ISA - APPLICATIONS TO ARRAY PROCESSING AND REAL-TIME COMPUTING This chapter considers the suitability of the ISA for vector/ array processing computers. We also consider the relationship of the ISA to wavefront processing and dataflow computing. We then describe a linear variant of the ISA known as the Linear ISA (LISA), which is an area efficient architecture. We then briefly indicate some possible application areas of the ISA: real-time robot control applications and high-speed vision systems.