The ASC model for parallel computation supports a generalization of an associative style of computing that has been used since the introduction of associative SIMD computers in the early 1970's. In particular, this model supports data parallelism, constant time maximum and minimum operations, one or more instruction streams (ISs) which are sent to an equal number of partition sets of processors (PEs), and assignment of tasks to the ISs using control parallelism. Since problems often need more processors than a machine has, it is useful to have virtual processors simulated by existing architectures. This paper shows how virtual parallelism is possible where more PEs and ISs are simulated than the actual hardware possesses. The extra time needed for an ASC(n,j) machine to simulate an ASC(N,J) machine where N ≥ n and J ≥ j is O(N/n + J/j + min(N/n, J) × min(n, J/j)) while the extra space required is O(N/n + J) per PE. The overall results provide an important step in defining the usability of the ASC model in terms of both existing one IS machines and future machines supporting multiple ISs.

This paper presents a new parallel algorithm far string matching with variable length "don't care" (VLDC). The initial computational model used is the associative computing model (ASC) enhanced with a linear network. ASC is a natural extension of the data parallel paradigm to a complete model far parallel computation. It supports massively parallelism through the use of data parallelism and constant time functions such as associative search and maximum value. It is also shown that the same algorithm is equally adaptable to the mesh with multiple broadcast. The algorithm has a run time of O(m) using O(n) processors, given a pattern of size m and a text of size n. The algorithm has the unique feature of permitting the identification of all match continuation points in the text after each "don't care" character.