High - performance implementation of algorithms on reconfigurable hardware

Abstract

This work is concerned with the design of high-performance digital circuits on Field-Programmable Gate Array (FPGA) devices. These are generic devices, offering reconfigurable hardware units for digital circuits to be loaded on. The work for this dissertation is two-fold and was motivated by practical problems, in the domains of Molecular Diagnostics and High Energy Physics, calling for high-performance implementations of a number of algorithms that map very well to FPGAs. As such, it is arranged in two main parts, one for each application. The first application is the development of a Canny edge detection algorithm for a real-time machine vision system that powers a microfluidic Lab-on-a-Chip demonstrator. The second application involves the redesign of various algorithms used in the FTK project, which uses FPGAs and Application-Specific Integrated Circuits (ASICs) to reconstruct the trajectories of the particles resulting from collisions inside the ATLAS detector, out of the traces they leave on the silicon detector layers, in real time. The algorithms designed deal with complex data management and Digital Signal Processing (DSP) tasks, and the novel implementations cope with the higher data rates of future scheduled upgrades. The compromises and approximations made in the algorithms and their justification; the strategies and methodologies followed in order to derive these implementations; and the performance metrics of the resulting designs, will be fully described in the subsequent chapters.

Το πόνημα που ακολουθεί αφορά τον σχεδιασμό ψηφιακών κυκλωμάτων υψηλών επιδόσεων σε συσκευές "προγραμματιζόμενες-στο-πεδίο διατάξεις πυλών" (FPGA). Αυτές είναι συσκευές γενικής χρήσης, προσφέροντας μονάδες επαναδιαρθρώσιμου υλικού για την υλοποίηση ψηφιακών κυκλωμάτων. Η δουλειά που παρουσιάζεται σε αυτήν τη διατριβή είναι διπλή, και κίνητρα για την πραγματοποίησή της αποτέλεσαν υπάρχοντα προβλήματα στους τομείς της Μοριακής Διαγνωστικής και της Φυσικής Υψηλών Ενεργειών με απαιτήσεις για υψηλών επιδόσεων υλοποιήσεις διαφόρων αλγορίθμων, που ταιριάζουν εξαιρετικά σε συσκευές FPGA. Ως εκ τούτου, είναι οργανωμένη σε δύο κύρια μέρη, ένα για την κάθε εφαρμογή. Η πρώτη εφαρμογή είναι η ανάπτυξη ενός αλγόριθμου ανίχνευσης ακμών, ονόματι Canny, για ένα σύστημα πραγματικού χρόνου που αποτελεί τη βάση ενός συστήματος επίδειξης για μικρορροϊκό εργαστήριο-σε-τσιπ. Η δεύτερη εφαρμογή είναι ο επανασχεδιασμός εκ νέου διαφόρων αλγορίθμων που χρησιμοποιούνται στο FTK, το οποίο χρησιμοποιεί FPGA και ASIC ώστε να ανακατασκευάζει σε πραγματικό χρόνο τις τροχιές των σωματιδίων που παράγονται από τις συγκρούσεις στον ανιχνευτή ATLAS, από τα ίχνη που αφήνουν στα στρώματα των ανιχνευτών πυριτίου. Οι αλγόριθμοι που αναπτύχθηκαν αφορούν περίπλοκες διαδικασίες αποθήκευσης και ανάκλησης δεδομένων και επεξεργασίας σήματος, με τις καινούριες τους υλοποιήσεις να πρέπει να ανταπεξέλθουν στις αυξημένες απαιτήσεις ροής δεδομένων που θα προκύψουν μετά τις μελλοντικές αναβαθμίσεις του ανιχνευτή. Οι συμβιβασμοί και οι προσεγγίσεις που χρησιμοποιήθηκαν στους διαφόρους αλγόριθμους και οι αιτιολογίες τους, οι στρατηγικές και οι μεθοδολογίες που ακολουθήθηκαν ώστε να γίνουν οι υλοποιήσεις, και τα χαρακτηριστικά και οι επιδόσεις των κυκλωμάτων που προέκυψαν, θα περιγραφούν πλήρως στα κεφάλαια που ακολουθούν.