Floorplanning and placement algorithms for 2.5 and 3 dimensional integrated circuits

In recent years, the evolution of electronic circuits has led to the development of increasingly complex technologies to increase the number of components positioned on the single chip, while the dimensions of the chips themselves have shrunk. For years the IC industry has been driven by Moore’s Law: the notion that by regularly reducing the minimum dimensions of its manufacturing processes, the functionality that fits on a single die will double every 18 to 24 months. Today, we are reaching the physical limits of miniaturization and designers also want to integrate more diverse functions in their chips: high-speed digital logic, analog, mixed-signal, a variety of sensors and other components. To increase functional integration more quickly than Moore’s Law, a new design approach (More than Moore) and new circuits are required. 3D circuits are the current solution to this problem: they are a type of circuits that grow not only in the two dimensions, but also in height. These circuits offer a large amount of opportunities to designers, but they present new set of challenges that don’t exist in more traditional circuits or cannot be dealt with the standard 2D IC design tools and algorithms. This work will focus on proposing two algorithms that can help the designers in the floorplanning and placement phases of the design process of a 3D circuit. The floorplanning algorithm can help the designer in selecting the best IC ordering in the stack, thus minimizing the number of through silicon vias (TSV) generated for the different floors of the circuits. This ordering is useful because minimizing the number of TSV in the circuit reduces its manufacturing cost and improves its performances and reliability. In the second phase, after the sorting, the placement algorithm will move the unconstrained logical links between the connectors trying to optimize their starting and arrival position and selects the best balls or TSVs in which the connections run. These choices are made in order to reduce the global wire lenght of the circuit while keeping the number of crossings contained to reduce the number of metallization layers used by the router and the cost of the entire circuit manufacturing. The experimental results show that the first algorithm always finds the best ordering of floors in the stack structures without exploring all the possible layouts (with a good gain in terms of time and memory required for this operation). The second algorithm provides very efficient solutions compared to a variety of random assignments (at least 60% less logical crossings between connections and 70% less physical wirelengths in the examined test cases).

Negli ultimi anni l’evoluzione dei circuiti elettronici ha portato allo sviluppo di tecnologie sempre più complesse per aumentare il numero di componenti posizionabili sul singolo chip, mentre le dimensioni dei chip stessi sono andate diminuendo. Per anni l’industria dei circuiti integrati è stata guidata dalle Legge di Moore: la nozione per cui ogni 18 – 24 mesi, utilizzando tecnologie sempre miniaturizzate nel processo di manifattura, il numero di transistor su un singolo “die” raddoppia. Oggi l’industria sta raggiungendo i limiti fisici per questa continua miniaturizzazione dei circuiti, inoltre i progettisti vogliono introdurre più funzioni sui chip come: logica ad alta velocità, aree analogiche, sezioni a segnale misto, molte tipologie di sensori ed altri componenti. Per incrementare l’integrazione di queste funzionalità più in fretta di quanto stimato dalla legge di Moore un nuovo approccio di progettazione (“More than Moore”) e nuovi circuiti sono necessari. I circuiti 3D sono la soluzione attuale a questa necessità: questa tipologia di circuiti non solo cresce nelle normali due dimensioni ma anche in altezza. Questi circuiti offrono molte possibilità ai progettisti, ma presentano anche un nuovo insieme di problematiche che non esistevano nei circuiti tradizionali e che non possono essere gestite facilmente mediante gli strumenti e gli algoritmi dedicati ai circuiti in 2D. Questo lavoro propone due algoritmi che possono aiutare i progettisti nelle fasi di floorplanning e placement del processo di sviluppo di un circuito 3D. Nella prima fase l’algoritmo di floorplanning supporta il progettista selezionando il migliore ordinamento, in funzione del numero di “through silicon via” generati, dei piani presenti nelle strutture a pila del circuito. Questo ordinamento è utile perché minimizzare il numero di TSV nel circuito riduce il suo costo di realizzazione e ne migliora l’integrità strutturale. Nella seconda fase, successiva all’ordinamento, l’algoritmo di placement sposta i collegamenti non vincolati tra i connettori cercando di ottimizzare il punto di partenza e arrivo della connessione e selezionando le migliori “ball” o TSV in cui far passare il collegamento. Queste scelte sono fatte con l’obiettivo di ridurre la lunghezza globale delle connessioni nel circuito mantenendo allo stesso tempo contenuto il numero di incroci generati, al fine di ridurre il numero di livelli di metallizzazione aggiunti dal router e di conseguenza il costo dell’intero circuito. I risultati sperimentali dimostrano che il primo algoritmo è sempre in grado di determinare il miglior ordinamento di piani nelle strutture a “stack” senza dover Chapter 0 20 esplorare tutte le possibili configurazioni (con un cospicuo guadagno in termini di tempo e memoria richiesta per questa operazione). Inoltre, nell’ambito del secondo algoritmo, mostrano che esso genera degli ottimi risultati rispetto a un grande numero di possibili assegnamenti casuali (n esaminati almeno 60% di incroci logici tra le connessioni in meno e una riduzione minima del 70% per quello che riguarda la lunghezza fisica delle connessioni).