SPARSE MATRIX COMPUTATIONS USING THE INTELLIGENT FILE STORE

Ahmad A. EL-ZEIN

In recent years, the application of associative processing to a variety of data processing problems has been considered. In this thesis, we investigate the application of the arithmetic capability offered by an associative system, and the storage capability offered by an associative memory, to solutions of sparse matrix computations. The solution of a set of sparse linear systems, stored in linear RAM-based memory, requires some ingenuity, but still a significant proportion of the computation time is devoted to the Read and Write access of the matrix. Such effort may be alleviated with the use of the associative memory on the Intelligent File Store (IFS). However, we have experimentally verified that the persistent gap between the memory-bound activity and the host-bound arithmetic operation causes slow run-time performance and, consequently, restricts the scope of IFS applicability in numerical computing.

But, it is a feature of the IFS that it has enhanced parallel-search capability which has been exploited in graph-oriented applications. We have done pioneering research in permuting a digraph to a block triangular form via graph theory. First, an efficient IFS algorithm for finding a full transversal in O(e/2+v) time is presented, where v is the number of nodes and e is the number of edges of the digraph being considered. Second, a competitive version of a breadth-depth search algorithm for finding the strong components of the digraph is also presented. The performance of these algorithms has been evaluated using the standard MA28 package as a basis for comparison. We have conducted numerical experiments which show the computation times for the IFS graph-based algorithms gain speed over the RAM graph­based algorithms. Thus, associative memory may be considered as a promising tool in offering scope for speed-up in more significant graph applications such as partitioning, tearing, etc.