Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/91212
Type: Thesis
Title: A mesh architecture for data management of matrix computations.
Author: Burdeniuk, Adam
Issue Date: 2014
School/Discipline: School of Electrical and Electronic Engineering
Abstract: 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.
Advisor: Lim, Cheng-Chew
Liebelt, Michael J.
Dissertation Note: Thesis (Ph.D.) -- University of Adelaide, School of Electrical and Electronic Engineering, 2014
Keywords: multiprocessor system-on-chip; data management; matrix algorithms; FPGA implementation; sequencing; synchronisation; on-chip communication
Provenance: This electronic version is made publicly available by the University of Adelaide in accordance with its open access policy for student theses. Copyright in this thesis remains with the author. This thesis may incorporate third party material which has been used by the author pursuant to Fair Dealing exceptions. If you are the owner of any included third party copyright material you wish to be removed from this electronic version, please complete the take down form located at: http://www.adelaide.edu.au/legals
Appears in Collections:Research Theses

Files in This Item:
File Description SizeFormat 
01front.pdf143.36 kBAdobe PDFView/Open
02whole.pdf1.78 MBAdobe PDFView/Open
PermissionsLibrary staff access only212.99 kBAdobe PDFView/Open
RestrictedLibrary staff access only2.05 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.