Πειραματική υλοποίηση σε Python για τη χωροταξική βελτιστοποίηση ολοκληρωμένων κυκλωμάτων με χρήση Normalized Polish Expression (NPE) και Simulated Annealing (SA). Το έργο επικεντρώνεται στη δημιουργία και βελτιστοποίηση slicing floorplans για σύνολα ορθογωνικών blocks σταθερών διαστάσεων, με βασικό κριτήριο την ελαχιστοποίηση του τελικού εμβαδού.
Το πρόβλημα του VLSI floorplanning αφορά την τοποθέτηση λειτουργικών μονάδων ενός ολοκληρωμένου κυκλώματος μέσα σε ένα συνολικό περίγραμμα chip. Στο συγκεκριμένο project, κάθε block έχει σταθερό πλάτος και ύψος και η διάταξη μοντελοποιείται ως slicing floorplan, δηλαδή ως διάταξη που προκύπτει από επαναλαμβανόμενες οριζόντιες και κατακόρυφες τομές.
Ο στόχος είναι η εύρεση μιας διάταξης με όσο το δυνατόν μικρότερο συνολικό εμβαδόν. Επειδή ο χώρος λύσεων αυξάνεται εκθετικά όσο αυξάνεται ο αριθμός των blocks, το πρόβλημα αντιμετωπίζεται με στοχαστική μεταευρετική αναζήτηση και όχι με εξαντλητική απαρίθμηση.
Η υλοποίηση:
- διαβάζει blocks από αρχείο CSV,
- αναπαριστά κάθε υποψήφια λύση ως NPE,
- αξιολογεί κάθε λύση με stack-based υπολογισμό,
- δημιουργεί γειτονικές λύσεις μέσω τεσσάρων ειδών κινήσεων,
- εφαρμόζει Simulated Annealing για αποδοχή ή απόρριψη νέων λύσεων,
- αποθηκεύει αποτελέσματα και δημιουργεί οπτικοποιήσεις των floorplans.
- Slicing floorplanning για hard rectangular blocks.
- Normalized Polish Expression ως συμπαγής αναπαράσταση λύσης.
- Stack-based evaluation για υπολογισμό πλάτους, ύψους και τελικού εμβαδού.
- Simulated Annealing με πιθανοτική αποδοχή χειρότερων λύσεων.
- Τέσσερις κινήσεις γειτονιάς για αναδιάταξη της NPE και περιστροφή blocks.
- Πειραματική αξιολόγηση σε προβλήματα 10, 100 και 150 blocks.
- Σύγκριση cooling rates 0.991, 0.995 και 0.999.
- Ανάλυση trade-off ανάμεσα σε τελικό εμβαδόν και υπολογιστικό κόστος.
- Pareto-based ερμηνεία των αποτελεσμάτων.
- Οπτικοποίηση αρχικών και τελικών διατάξεων με Matplotlib.
.
├── main.py # Κύρια υλοποίηση του αλγορίθμου
├── blocks.csv # Δεδομένα εισόδου: id, width, height
├── explanation.md # Αναλυτική επεξήγηση συναρτήσεων και λογικής
├── results.txt # Καταγεγραμμένα αποτελέσματα εκτελέσεων
├── SimulatedAnnealingRESULTS.xlsx # Συγκεντρωτική ανάλυση πειραματικών αποτελεσμάτων
├── SimulatedAnnealing.pdf # Συνοδευτικό υλικό / αναφορά
├── SAplots.pdf # Συγκεντρωτικά plots
└── plots/ # Εικόνες αρχικών, τελικών και συγκριτικών διατάξεων
Η λύση αναπαρίσταται ως λίστα από tokens:
- Operands: τα IDs των blocks, π.χ.
"1","2","35". - Operators: οι τελεστές
HκαιV.
Οι τελεστές δηλώνουν τον τρόπο σύνθεσης δύο υποδιατάξεων:
| Operator | Ερμηνεία | Υπολογισμός διαστάσεων |
|---|---|---|
H |
Οριζόντια σύνθεση, το ένα block πάνω από το άλλο | width = max(w1, w2), height = h1 + h2 |
V |
Κατακόρυφη σύνθεση, το ένα block δίπλα στο άλλο | width = w1 + w2, height = max(h1, h2) |
Η αξιολόγηση γίνεται με στοίβα. Κάθε block εισάγεται στη στοίβα ως ζεύγος (width, height), ενώ κάθε operator αφαιρεί τα δύο τελευταία στοιχεία, τα συνδυάζει και επιστρέφει ένα νέο σύνθετο block. Στο τέλος, το μοναδικό στοιχείο της στοίβας αντιστοιχεί στο συνολικό floorplan.
Ο αλγόριθμος ξεκινά από μια αρχική NPE και επαναληπτικά δημιουργεί γειτονικές λύσεις. Αν η νέα λύση έχει μικρότερο εμβαδόν, γίνεται αποδεκτή. Αν είναι χειρότερη, μπορεί να γίνει αποδεκτή με πιθανότητα:
P = exp(-Δ / T)
όπου:
Δείναι η διαφορά κόστους μεταξύ νέας και τρέχουσας λύσης,Tείναι η τρέχουσα θερμοκρασία.
Η θερμοκρασία μειώνεται σταδιακά με cooling factor r:
T = T * r
Στα πειράματα εξετάζονται οι τιμές:
r ∈ {0.991, 0.995, 0.999}
Ο αλγόριθμος περιλαμβάνει επίσης μηχανισμό reheating, ώστε να αυξάνεται προσωρινά η θερμοκρασία όταν συσσωρεύονται πολλές απορρίψεις και η αναζήτηση τείνει να εγκλωβιστεί.
Η μετάβαση από μια λύση σε μια γειτονική λύση γίνεται μέσω τεσσάρων κινήσεων:
| Move | Περιγραφή | Ρόλος |
|---|---|---|
M1 |
Ανταλλαγή δύο γειτονικών tokens ίδιου τύπου | Ήπια τοπική μεταβολή |
M2 |
Αντιστροφή υποαλυσίδας της NPE | Πιο έντονη αναδιάταξη |
M3 |
Ελεγχόμενη τοπική ανταλλαγή e(i) με e(i+1) |
Μικρομετατόπιση με περιορισμούς |
M4 |
Περιστροφή block μέσω ανταλλαγής width και height | Γεωμετρική διαφοροποίηση χωρίς αλλαγή σειράς tokens |
Στην πειραματική διαδικασία χρησιμοποιούνται τέσσερα διαφορετικά προφίλ βαρών για τις κινήσεις:
| Case | M1 | M2 | M3 | M4 |
|---|---|---|---|---|
| Case 1 | 0.5 | 0.2 | 0.2 | 0.1 |
| Case 2 | 0.2 | 0.2 | 0.1 | 0.5 |
| Case 3 | 0.2 | 0.1 | 0.5 | 0.2 |
| Case 4 | 0.1 | 0.5 | 0.2 | 0.2 |
Το αρχείο blocks.csv περιέχει τα blocks που θα χρησιμοποιηθούν από τον αλγόριθμο. Η αναμενόμενη μορφή είναι:
id,width,height
1,20,40
2,35,15
3,10,25Κάθε γραμμή αντιστοιχεί σε ένα hard block με σταθερές διαστάσεις.
Η υλοποίηση βασίζεται σε Python 3.x και χρησιμοποιεί κυρίως standard library modules. Για την οπτικοποίηση απαιτείται η βιβλιοθήκη Matplotlib.
pip install matplotlibΠροτεινόμενη εγκατάσταση σε virtual environment:
python -m venv .venv
source .venv/bin/activate # Linux / macOS
# .venv\Scripts\activate # Windows
pip install matplotlibΑπό τον φάκελο του repository:
python main.pyΣτην τρέχουσα μορφή του κώδικα, οι βασικές πειραματικές παράμετροι ορίζονται μέσα στο main.py, όπως:
n = 10
E = ['6', '5', '2', 'H', '7', '10', '4', 'H', 'V', '3', '9', '8', 'V', '1', 'H', 'V', 'H', 'V', 'H']
T = 100
r = 0.999Για διαφορετικά πειράματα, τροποποιούνται το πλήθος των blocks, η αρχική NPE και ο ρυθμός ψύξης.
Κατά την εκτέλεση, ο αλγόριθμος εμφανίζει:
- την αρχική NPE,
- το αρχικό εμβαδόν,
- την καλύτερη τελική NPE,
- το τελικό εμβαδόν,
- τον αριθμό επαναλήψεων,
- τον χρόνο εκτέλεσης,
- την αρχική και την τελική διάταξη ως Matplotlib plots.
Επιπλέον, παράγονται ή ενημερώνονται αρχεία όπως:
csvVersion_results.txt, για αποθήκευση τελικών runs,temperature_log.csv, για παρακολούθηση θερμοκρασίας και κόστους ανά επανάληψη,results.txt, ως συγκεντρωτικό αρχείο αποτελεσμάτων που υπάρχει ήδη στο repository.
Η πειραματική αξιολόγηση οργανώθηκε σε τρεις ομάδες προβλημάτων:
| Ομάδα | Πλήθος blocks | Σκοπός |
|---|---|---|
| Group 1 | 10 | Μικρή κλίμακα και γρήγορη παρατήρηση συμπεριφοράς |
| Group 2 | 100 | Μεσαία κλίμακα και αυξημένη συνδυαστική πολυπλοκότητα |
| Group 3 | 150 | Μεγαλύτερη κλίμακα και πιο απαιτητική αναζήτηση |
Για κάθε ομάδα εξετάστηκαν:
- 3 cooling rates:
0.991,0.995,0.999, - 4 περιπτώσεις βαρών κινήσεων,
- πολλαπλές αρχικές NPE εκφράσεις.
Συνολικά, από 394 εκτελέσεις της τελικής μορφής του κώδικα διατηρήθηκαν 180 αντιπροσωπευτικές εκτελέσεις για την κύρια ανάλυση.
Παράδειγμα αρχικής και τελικής διάταξης από τα διαθέσιμα plots του repository:
| Initial floorplan | Final floorplan |
|---|---|
 |
 |
Τα αποτελέσματα δείχνουν ότι ο συνδυασμός NPE και Simulated Annealing μπορεί να παράγει πιο συμπαγείς και αποδοτικές slicing διατάξεις. Η ποιότητα της τελικής λύσης επηρεάζεται σημαντικά από:
- τον cooling rate,
- το αρχικό σημείο εκκίνησης,
- την κατανομή πιθανοτήτων των κινήσεων,
- το μέγεθος του προβλήματος.
Γενικά, ταχύτερη ψύξη μπορεί να οδηγήσει σε μικρότερο χρόνο εκτέλεσης, ενώ πιο αργή ψύξη επιτρέπει εκτενέστερη εξερεύνηση του χώρου λύσεων. Η τιμή 0.995 λειτουργεί ως πρακτικό ενδιάμεσο σημείο, ενώ η 0.999 είναι πιο ελκυστική όταν δίνεται προτεραιότητα στην ποιότητα της λύσης έναντι του χρόνου.
Η χρήση trade-off curves και Pareto fronts βοηθά στην ερμηνεία των αποτελεσμάτων όχι μόνο με βάση το τελικό εμβαδόν, αλλά και με βάση τη σχέση ποιότητας λύσης και υπολογιστικού κόστους.
Η παρούσα υλοποίηση αποτελεί πειραματικό πλαίσιο και όχι βιομηχανικό εργαλείο φυσικού σχεδιασμού. Βασικοί περιορισμοί:
- η συνάρτηση κόστους εστιάζει κυρίως στο τελικό εμβαδόν,
- δεν ενσωματώνονται wirelength, thermal constraints ή routing complexity,
- τα αποτελέσματα είναι στοχαστικά και μπορεί να διαφέρουν ανά εκτέλεση,
- η χρήση σταθερών random seeds θα βελτίωνε την πλήρη επαναληψιμότητα,
- η προσέγγιση αφορά slicing floorplans και όχι γενικά non-slicing floorplans.
Πιθανές επεκτάσεις του project:
- adaptive cooling schedule,
- μεγαλύτερα benchmark datasets,
- πολυκριτηριακή συνάρτηση κόστους,
- σύγκριση με Genetic Algorithms, Tabu Search ή υβριδικές τεχνικές,
- σύγκριση NPE με Sequence Pair ή B*-Tree αναπαραστάσεις,
- αυστηρότερη στατιστική αξιολόγηση των αποτελεσμάτων,
- πλήρως αναστρέψιμος μηχανισμός περιστροφής blocks.
Kiousis Konstantinos
Department of Computer Science & Telecommunications
School of Science
Δεν έχει οριστεί ακόμη άδεια χρήσης στο repository. Αν το project πρόκειται να διανεμηθεί δημόσια ή να χρησιμοποιηθεί από τρίτους, προτείνεται η προσθήκη κατάλληλου LICENSE αρχείου.