A design methodology for an innovative parallel controller in high level synthesis

This thesis work proposes a design methodology to build a parallel controller in high-level synthesis, able to handle with the parallelism problem. The proposed controller is able to automatically identify the conditions that enable the execution of an instruction as soon as the dependencies and the resource constraints are satisfied. Such conditions are obtained through a parallelism identification phase, performed by means of the analysis of a novel intermediate representation, properly defined to represent the inherent parallelism. In the proposed architecture, the task of assign a control step in which each instruction will be executed is implicitly performed at run-time by the parallel controller. The proposed controller structure is not composed of a set of communicating local finite state machines. It is instead closer to a behavioral description of the specification composed of several modules, interacting according to a token-based scheme, which is a very simple communication paradigm. This choice prevents to incur in the communication overhead problem. Moreover, it is obtained through a bottom-up approach. In this way, the entire finite state machine construction is not needed, avoiding also the problems related to decomposition techniques. Finally, making the controller able to identify by itself the conditions that enable instructions execution led to face another aspect of the parallelism issue, that is the parallelism formalization. Such problem consists in how to formalize the information about the parallelism, obtained from the analysis of the proposed IR, in such a way to make the controller able to understand and automatically manage this information. Since the controller is able to manage signals, such information has been formalized as a composition of signals, indicating when the execution can start, i.e. when the above mentioned conditions are satisfied. Such composition of signals defines a function associated with each instruction. Similarities with Boolean Algebra makes such functions easily manageable and optimizable by means of standard techniques.

Il presente lavoro di tesi propone una metodologia di progetto, integrata nella sintesi ad alto livello, per la costruzione di un controllore parallelo che affronti il problema dell’estrazione del parallelismo. Il controllore parallelo proposto è in grado di identificare autonomamente e a run-time le condizioni che vincolano l’esecuzione delle istruzioni e abilitarne l’esecuzione il prima possibile, ovvero non appena le dipendenze e i vincoli sulle risorse sono soddisfatti. Tali condizioni vengono ricavate tramite l’analisi di una nuova rappresentazione, appositamente definita per rappresentare il parallelismo. Questo controllore non è composto da un insieme di macchine a stati locali comunicanti, ma è più simile ad una descrizione comportamentale della specifica, composto da diversi moduli, che interagiscono secondo uno schema basato su token, che rappresenta un paradigma di comunicazione molto semplice. Questa scelta permette di evitare il problema dell’overhead di comunicazione. Il controllore parallelo, inoltre, è ottenuto tramite un approccio dal basso verso l’alto. In tal modo non è necessaria la costruzione dell’intera macchina a stati, evitando i problemi legati alle tecniche di decomposizione. Infine, l’aver dotato il controllore della capacità di identificare autonomamente le suddette condizioni ha portato a dover affrontare il problema della formalizzazione del parallelismo. Tale problema consiste nel trovare un modo per formalizzare l’informazione sul parallelismo in modo tale che il controllore possa capirla e gestirla automaticamente. Poiché il controllore è in grado di gestire segnali, tale informazione è stata formalizzata come una composizione di segnali, che indica il momento in cui un’istruzione può essere eseguita, ovvero quando le suddette condizioni sono soddisfatte. Tale composizione di segnali definisce una funzione associata a ciascuna istruzione. Le affinità con l’algebra di Boole rendono tali funzioni facili da ottimizzare per mezzo di tecniche standard.