A mesh architecture for data management of matrix computations.

Using super-resolution techniques to estimate the direction that a signal arrived at a radio receiver; Tracking moving targets using particle filters; Applying advanced coding techniques to radio transmissions. Real-world applications like these rely on high-speed matrix computations. Although the computational ability of general-purpose computer architectures is growing, some numerically intensive calculations (such as those above) may benefit from specialised matrix processing hardware. Work in this thesis builds on earlier dense matrix accelerators, which were previously implemented as coprocessors attached to general purpose processor cores. It is well known that matrix algorithms are highly parallelisable, so the coprocessor generally contains many cores to take advantage of this. However, encapsulating them within the coprocessor often prohibits their use in non-matrix computations. This limitation is addressed by the Matrix Data Management Layer (MDML), described in this thesis. The MDML doesnt share the coprocessor-based architecture of earlier systems. Growing transistor budgets have made it feasible to embed general purpose Commercial Off-The-Shelf (COTS) processors within the MDML. Programming is simplified as the system is homogeneous, and programmers can use familiar tools and languages. Having general-purpose processors embedded throughout the array also opens the possibility to process more than just dense matrix data. Requirements for the MDML were synthesised by analysing common features and operations in matrix algorithms. This analysis found that data management (including sequencing, distribution and efficient reuse of data) was a significant overhead. Thus, the MDML focuses on accelerating these tasks, which are common to more than just matrix algorithms. Effort was also directed into integrating COTS components to reduce design effort, which resulted in a layered hardware design. The MDML integrates off-the- shelf memory and processing cores into a scalable on-chip mesh array. The MDML uses a flexible sequencing regime capable of autonomously generating memory access patterns for a variety of complex data structures. This sequencer has been tested by construction of a hardware prototype. A programming style based on sequences of instruction snippets was also developed and shown effective for loop-based algorithms. A flexible, low-latency data transport allows the MDML to use fine-grain communication. Improved array synchronisation techniques were also proposed and implemented. These techniques reduce the performance impact of barrier synchronisation, and also reduce the frequency with which the array must synchronise. The MDML concept was verified using both hardware modelling and theoretical analysis: • Hardware modelling was used to verify the completeness and correctness of the architecture, and demonstrated that the MDML is practical to implement in current hardware. • Analytic models of performance were developed for algorithms mapped to a theoretical MDML system. These were used to evaluate performance, scalability and programmability of the MDML. Algorithms that were mapped include conformal matrix multiplication, LU decomposition and forward substitution. Thus, it is concluded that the MDML architecture provides a realistic and efficient way of achieving high-speed matrix computation.

Author dc:creator

• Burdeniuk, Adam

Advisors dc:contributor.advisor

• Lim, Cheng-Chew
• Liebelt, Michael J.

• multiprocessor system-on-chip; data management; matrix algorithms; FPGA implementation; sequencing; synchronisation; on-chip communication

Handle dc:identifier.uri

http://hdl.handle.net/2440/91212

OAI identifier oai:identifier

oai:digital.library.adelaide.edu.au:2440/91212