SEARCHING ALGORITHMS IMPLEMENTED ON PROBABILISTIC SYSTOLIC ARRAYS
Ivan Kramosil · International Journal of General Systems · 1996
A number of processors working simultaneously make sequential random samples from a large basic space and test the sampled elements in order to discover at least one possessing a given investigated property. In the most simple case, all the random samples are statistically independent, but more sophisticated arrays with dependent samples are also considered. The sampled elements with the tested property, or pieces of information saying that particular processors have not discovered such an element, are processed by a hierarchy of higher-level processors, finally, an output processor yields a “yes” or “no” answer to the question whether there is at least one element possessing the tested property in the basic space. Due to the random nature of the sampling mechanism and due to the fact that communications among processors are supposed to be weighted by a positive probability of error, the final answer may be wrong with a positive probability. The aim is to minimize the time computational complexity of the statistical decision function defined by the systolic array in question under the condition that the probability of error be kept below an a priori given threshold value