Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Several vendors such as Cray, Fujitsu, NEC supply vector processors that use pipelined functional units. A pipelined functional unit can extract parallelism by operating on a stream of operands simultaneously, with each stage in the pipeline working on a different set of operands. Users of these machines typically program in FORTRAN, and rely on an optimizing compiler (vectorizer) to extract parallelism. These compilers analyze loops in a program and generate a vector instruction for each type of operation that can be performed simultaneously on different elements of an array. When the independence of operations on different elements of an array is not compile-time determinable, as for example is the case with unstructured sparse matrix computations, these compilers generate scalar code. In this paper we propose a scheme based on run-time dependence analysis to vectorize loops with dependencies unknown at compile-time. Our approach analyses a loop at run-time by executing a skeleton of the loop and assigns a level to each operation. Operations that are independent of any other operations in the loop are given a level of one. Other operations are given a level one greater than the maximum of levels of all dependent operations. A vector instruction, using indirect operand access, is generated for all the operations of a given type at each level. The approach was evaluated by implementing a sparse triangular solver on one processor of a Cray X-MP. A number of sparse matrices derived from the application domain of circuit simulation were used. An improvement in performance ranging between 100-500.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Array and vector processors

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Design, Languages