Discrepancy analysis: a methodology for automated bug detection in hardware designs generated with high-Level synthesis

The thesis describes the definition, implementation, and evaluation of a methodology for automated bug detection, called Discrepancy Analysis, targeted at hardware designs generated with High-Level Synthesis. Discrepancy Analysis is based on a notion of equivalence between the execution of the hardware generated with High-Level Synthesis and the execution of the software obtained from the original high-level source code used to generate that hardware. Using this notion of equivalence, the thesis describes how to compare automatically the two executions, and how to detect and isolate the first mismatch if present. All these operations are executed without human interaction, relieving users from the time-consuming and error-prone tasks to select the necessary signals for debugging, analyzing the signal traces to identify the malfunction, and backtracking it to the original high-level source code. The methodology is tightly integrated with the High-Level Synthesis process. As a consequence, it supports all compiler optimizations available during High-Level Synthesis. This coupling with the High-Level Synthesis tool also allows to automatically select in the generated designs the signals necessary for automated bug detection. Despite the tight coupling with the High-Level Synthesis tool, the discussion is kept as general as possible and only relies on common features that are present in all the known commercial and academic tools. The thesis also describes two extensions of Discrepancy Analysis: one to support automated bug detection in hardware generated with High-Level Synthesis of multithreaded code; one to support automated bug detection on pointers and memory accesses. Two bug detection flows based on Discrepancy Analysis are presented. The first is based on simulation of the hardware at the Register Transfer Level and performs the automated bug detection process offline after execution. The second flow is for on-chip bug detection. The generated hardware is instrumented with dedicated checker components, that analyze the execution on the fly, halting the circuit if a mismatch occurs and notifying it to users. Both the debug flows have been implemented and tested with BAMBU , an open source research framework for High-Level Synthesis developed at Politecnico di Milano. The results have been evaluated in terms of performance, coverage, and other advantages brought to the overall debugging experience, like the considerable reduction of the size of the waveforms files that can be achieved with a heuristic for automated signal selection. This evaluation showed Discrepancy Analysis to be fast, accurate, and effective in identifying several different classes of bugs, coming from the original high-level code, from external libraries of components, and even subtle bugs injected by the High-Level Synthesis tool itself. A thorough and extensive analysis of these classes of bugs has been carried on, both on the baseline version and on the presented extensions for multithreaded code, for pointers, and for on-chip debugging. The technique used to compress the execution traces for On-Chip Discrepancy Analysis, based on Efficient Path Profiling, also showed reductions of the memory consumption necessary for on-chip debugging up to 95% compared to previous state-of-the-art.

La tesi descrive la definizione, l'implementazione, e la valutazione di una metodologia, chiamata Discrepancy Analysis, per l'identificazione automatica di bug in design hardware generati con High-Level Synthesis. Questa metodologia è basata su una nozione di equivalenza tra l'esecuzione dell'hardware generato con High-Level Synthesis e l'esecuzione del software ottenuto dal codice di alto livello usato per generare tale hardware. Attraverso questa nozione di equivalenza, la tesi descrive come confrontare automaticamente le due esecuzioni, identificando ed isolando la prima discrepanza, se presente. Tutte queste operazioni vengono eseguite senza interazione umana, sollevando gli utenti dall'onerosa analisi manuale dei segnali normalmente necessaria per identificare i malfunzionamenti. Gli errori sono trovati in automatico e ricondotti al codice di alto livello ad essi associato. La metodologia proposta è strettamente integrata con il processo di High-Level Synthesis, supportando in questo modo tutte le ottimizzazioni possibili in fase di compilazione senza perdita di accuratezza. Questa integrazione permette anche di selezionare automaticamente nel design generato il minimo numero di segnali che sono secessari per identificare i bug in modo automatico. Nonostante la stretta relazione tra la Discrepancy Analysis e lo strumento di High-Level Synthesis usato per la sua implementazione, la definizione della metodologia è stata mantenuta generale, sfruttando solo caratteristiche comuni a tutti i tool commerciali e accademici, in modo da non perdere generalità. La tesi descrive anche due estensioni della Discrepancy Analysis: la prima serve ad identificare i bug in circuiti generati con High-Level Synthesis da codice multithreaded; la seconda per poter analizzare anche bug che coinvolgono puntatori e accessi in memoria. La tesi presenta inoltre due diversi flussi di Discrepancy Analysis. Il primo è basato su simulazione dell'hardware ed esegue il confronto delle comportamento di hardware e software dopo l'esecuzione, offline. Il secondo flusso invece serve per identificare bug on-chip. In questo secondo caso l'hardware generato è instrumentato con dei checker dedicati, che analizzano l'esecuzione durante il funzionamento del circuito, interrompendolo in caso di malfunzionamento e riportando l'errore identificato. Entrambi i workflow sono stati implementati e testati in BAMBU, un framework di ricerca open source che comprende anche un compilatore per High-Level Synthesis, sviluppato al Politecnico di Milano. I risultati sono stati valutati in termini di performance, coverage, altri vantaggi che la metodologia porta all'esperienza di debugging, come per esempio la riduzione delle forme d'onda necessarie per analizzare il comportamento del design. Questa valutazione ha dimostrato che la Discrepancy analysis è veloce, accurata, ed efficace nell'identificazione di svariate classi di bug. Un'analisi accurata e approfondita è stata effettuata anche sulle estensioni per il codice multithreaded, per il supporto ai puntatori, e per il debugging on-chip. In questo ultimo caso le tecniche usate per l'implementazione dei checker hanno permesso di ridurre il consumo di memoria su FPGA fino al 95% rispetto al precedente stato dell'arte.