Dependence Analysis and Architecture Design for Bit-Level Algorithms
Authors:
- 1 August 1993
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (01903918) , 30-38
Abstract
In designing application-specific bit-level architectures and in programming existing bit-level processor arrays, it is necessary to expand a word-level algorithm into its bit-level form before dependence analysis can be performed. In this paper, we consider dependence structures of bit-level algorithms as functions of three components dependence structures of word-level algorithms, dependence structures of the arithmetic algorithms implementing word-wise operations, and algorithm expansions. Based on these components, we can derive dependence structures of bit-level algorithms without using time consuming general dependence analysis methods. To illustrate our approach, we derive two dependence structures for bit-level matrix multiplication and apply a method developed earlier [5,6,10] to design two bit-level architectures. One of these architectures is O{p) times faster than the best word-level architecture, where p is the word length. The speedup we found here is true in general because a bit in a bit-level architecture goes to the next processor for processing as soon as it is available.Keywords
This publication has 5 references indexed in Scilit:
- Dependence Analysis and Architecture Design for Bit-Level Algorithms1993
- On time mapping of uniform dependence algorithms into lower dimensional processor arraysIEEE Transactions on Parallel and Distributed Systems, 1992
- Dependence Analysis for Supercomputing1988
- The Design of Optimal Systolic ArraysIEEE Transactions on Computers, 1985
- Data broadcasting in linearly scheduled array processors1984