Binary relational processing on high performance array processors

Abstract

Herein, an enhanced square array processor which is the mapping of the binary relational algebra composition operator is investigated. The processor, which can compose a new binary relation from two existing ones, attempts to eliminate the complications added to the processing procedure because of the partitioning applied to the long input relations under processing. A part of an input relation must be processed with all parts of the other input relation, so as a new relation to be composed. The processor under investigation, consisting of n2 processing elements - pe, using as inputs its two sides of n pe each and applying parallel processing techniques, can process concurrently multiple parts of relations having length n. The complexity of the corresponding concurrent processing algorithm is low, ensuring the high performance of the proposed processor. It can be used to improve considerably the efficiency of the binary relations algebra based advanced applications, such as object oriented software architecture restructuring and object oriented parallel query processing. © 2009 American Institute of Physics.