{'fraction_non_alphanumeric': 0.015600624024960999, 'fraction_numerical': 0.0, 'mean_word_length': 4.956656346749226, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Interval graph algorithms for two-dimensional multiple folding of array-based VLSI layouts

Folding or topological compaction of array-based VLSI layouts is an important optimization step that is carried out after logic synthesis. In this paper, a new approach to two-dimensional multiple folding of array-based VLSI layouts is presented. From the specification of the problem a pair of intersection graphs is created. We show that any pair of interval graphs that contain the intersection graphs as spanning subgraphs corresponds to a set of feasible foldings. Next, a complete and exact characterization of the folding problem is presented. In particular, it is shown that the set of all feasible foldings associated with a given pair of interval graphs corresponds to the set of independent colorings of a pair of compatibility graphs. The compatibility graphs are derived from a pair of interval graphs that contain the intersection graphs as spanning subgraphs. Thus, minimizing the area of a layout is tantamount to finding a pair of compatibility graphs such that the product of their chromatic numbers is minimum. As important as minimizing the area of a layout is, the ability to rapidly generate compact layouts over a wide range of aspect ratios is often equally, if not more, important. The interval graph-based formulation of the folding problem permits a controlled and systematic generation of compact layouts with varying aspect ratios. Efficient and provably correct algorithms to generate compact layouts that have a given number of rows or a given number of columns within their minimum and maximum possible values are given. The basic theory and methods are extended to include I/O and other types of constraints. Finally, the results of experiments that were carried out on a large number of benchmark problems are given. These results are compared with those obtained by previously reported methods. >