NEW ALGORITHMS FOR MATRIX OPERATIONS WITH APPLICATIONS TO A RECONFIGURABLE PARALLEL ARCHITECTURE

We present new algorithms for matrix operations that can be applied to wards efficient implementation on a reconfigurable parallel architectu re. We attempt to minimize the movement of information by instead 'mov ing' (reconfiguring the relative proximity of) the PEs. We aim to comp lete most communication requests with only two levels of routing decis ions among a small set of channels. as a model we propose using a nove l reconfigurable architecture that is the target for our new matrix op erations algorithms. we show that, under certain conditions, our new a lgorithms will be better than any other algorithms previously suggeste d. The technique we used to developed the new matrix operation algorit hms, can be applied to other applications as well that exhibit similar switching behavior. Many parallel applications have persistent commun ication patterns. These patterns, at times not regular, can be viewed as if each Processing Element (PE) communicates with a small group of other PEs. Switching locality means that the need to 'switch' or route the information to or from each PE is limited to a small set of sourc es or destinations. The physical location of these sources and destina tions is not important as long as the connection degree is moderate. U sing the power of reconfiguration and the speed of the small crossbar switches (interconnection caches), the performance of such application s might be improved. Our solutions can be applied to future massively parallel processing with reconfigurable network. the need of reconfigu ration may be a dominant factor of future architectures that employs o ptical interconnection networks, as optics cannot perform logical oper ations needed in a network, in an economic way. Thus the possibility o f reconfiguration is an important one to address, and in turn to come with new algorithms optimize for this made of operation.