Απαρίθμηση και κωδικοποίηση τεμαχισμένων κατόψεων

Abstract

Η κατασκευή κατόψεων (floorplanning), γίνεται όλο και πιο σημαντική στον σχεδιασμό των VLSI κυκλωμάτων και χρησιμοποιείται ευρέως για να μειωθεί ο χρόνος πολυπλοκότητας της κατασκευής τους. Δυστυχώς, πολλά προβλήματα σχεδιασμού κατόψεων είναι NP, δηλαδή απαιτούν μεγάλο χρόνο επίλυσης. Η αναπαράσταση κατόψεων είναι μία θεμελιώδης αρχή, επειδή η αποδοτικότητα των βασικών λειτουργιών τους, βασίζεται στην γεωμετρική έκφραση των τεμαχίων τους Υπάρχουν δύο σημαντικά χαρακτηριστικά, για την αναπαράσταση μίας κάτοψης .Το πρώτο χαρακτηριστικό αφορά τον αριθμό των συνδυασμών αναπαράστασης. Η αναπαράσταση πρέπει να γίνεται από έναν διακεκριμένο κωδικό, όμως είναι πιθανό, δύο διακεκριμένοι κωδικοί να αντιστοιχούν στην ίδια κάτοψη. Αυτή η περίπτωση αναφέρεται και ως πλεονασμός της αναπαράστασης. Το δεύτερο χαρακτηριστικό, είναι ο χρόνος πολυπλοκότητας της μετατροπής του διακεκριμένου κωδικού αναπαράστασης στην αντίστοιχη κάτοψη. Επειδή αυτή η μετατροπή είναι η πιο συχνά χρησιμοποιούμενη μετατροπή, θέλουμε ο χρόνος πολυπλοκότητας να είναι όσο μικρός όσο γίνεται. Η γεωμετρική σχέση μεταξύ των τεμαχίων, καθορίζεται από την ορθογωνική τομή της περιοχής μιας κάτοψης. Η κάτοψη χωρίζεται σε ορθογωνικές έδρες και κάθε έδρα χωρίζεται με ορθογωνικές τομές σε νέες έδρες.