Progetto sull'ottimizzazione dei registri utilizzando graph coloring sul grafo di incompatibilità. Il programma riceve in ingresso un file .txt, contenente al suo interno:
- Variabile;
- Operazione assegnata alla variabile;
- Cicli di clock in cui rimane in vita.
Per disegnare il grafo di incompatibilità [Grafo che rappresenta un vertice per ogni variabile e un arco fra due variabili se queste sono attive nello stesso ciclo di clock], bisogna prima determinare per ogni ciclo di clock, quali variabili sono attive, e quali no. Utilizzando la funzione Incompatibility_graph(life_cycle), a cui passiamo una lista di liste contenente le variabili attive per ogni ciclo di clock, riusciamo così a disegnare il grafo di incompatibilità.
Da qui riusciamo a determinare il numero massimo di registri che possiamo utilizzare, andando a calcolare, per ogni ciclo di clock, quale tra questi ha il numero massimo di operazioni attive in quel momento.
ES: [['u0', 'u1', 'u2', 'u3'],['u4', 'u5'],['u5', 'u6'],['u5', 'u7'],['u5', 'u8'],['u9']] --> Nel primo ciclo di clock ci sono attive le operazioni u0,u1,u2,u3, nel secondo ciclo di clock ci sono attive u4,u5 e così via. Per cui il numero di registri da utilizzare è 4.
Una volta determinato il numero massimo di registri che si devono utilizzare, andiamo ad assegnare ad ognuno di essi le variabili, questo processo viene chiamato binding.
Per effettuare questo compito esistono degli algoritmi euristici di tipo greedy, ma questo codice permette di andare ad inserire l'operazione nel primo registro libero, senza vincoli di spazio.
Una volta assegnato un colore ad ogni nodo, dove ogni nodo comunicante nel grafo di incompatibilità ha un colore diverso, lo rappresento graficamente, determinando così per ogni registro quale operazione e quale colore è assegnato.
Infine, dato il coloring graph, passiamo alla descrizione RTL dell'algoritmo, rappresentandolo così a terminale.
FUNZIONAMENTO CODICE
Al run dello script python, chiederà a terminale di scrivere il file che si vuole utilizzare tra quelli proposti (ES: DFG6.txt).
Nel caso in cui si voglia aggiungere un file proprio, bisogna seguire lo schema "variabile; operazione;clock", come mostrato nella prima figura.
Consecutivamente stamperà il grafo di incompatibilità, a cui segue il coloring graph, e la descrizione RTL.