The Effect of Interword Connectivity in Associative Processing

Abstract

Technology advances enable the design of powerful associative processors. Conventional approaches have resulted in architectures, which can store multiple numbers (fields) in a single memory word and can perform arithmetic operations within each word in parallel. Currently, interword communication for parallel processing is performed over a simple interconnect such as a star network with the comparand register as the hub. We follow an alternative approach and we focus on improved interword connectivity rather than highly sophisticated memory word structures. We introduce an associative processor with a single-stage hypercube interconnection among memory words, and with the word-network interface providing routing function and small buffering (two field-size memory buffers, one for transmission and one for reception). This leads to an efficient, low-cost system that allows parallel data transfers and achieves dramatic performance improvements for numerical applications, as we demonstrate introducing efficient algorithms for matrix multiplication and for 1-D and 2-D FFT, achieving linear and logarithmic complexity, respectively. In addition to the hypercube, we analyze the performance effect of additional interword connectivity: unidirectional and bidirectional shifting between adjacent words. We also demonstrate that the improved interword connectivity results in several efficient primitive operations for numerical applications, such as bit-reversal and perfect-shuffle.