Grand Challenges |
A Parameterized Linear Array with a Reconfigurable Pipelined Bus System: LARPBS(p)
Department of Computer Science, The University of Texas at El Paso, El Paso, TX 79968-0518, USA
The linear array with a reconfigurable pipelined bus system (LARPBS) is an optical bus-based theoretical parallel computation model. Many parallel algorithms have been proposed using this model of computation. However, a current limitation of the LARPBS model is that it does not provide for performance prediction of these algorithms running on realistic implementations of the LARPBS model. This paper investigates the parameterization of the LARPBS model so as to overcome this limitation. Specifically, a new parameterized parallel computation model, the LARPBS(p) model, is proposed in this paper. The LARPBS(p) model captures computational costs through six abstract parameters: the number of processors, the communication latency, the communication overhead, the network capacity, the computation time and the synchronization time. The proposed parameters and, subsequently, the cost analysis on the LARPBS(p) model are presented. In addition applications of the cost analysis to some primitive operations and to two matrix multiplication algorithms on the LARPBS(p) are also presented. LARPBS(p) is intended to serve as a basis for a more accurate estimation of execution time of algorithms by providing greater detail of the costs involved on the LARPBS.
Received 25 November 2003. Revised 27 September 2004.