[image] [image] Ressource protégée - Archive ouverte HAL Accéder directement au contenu

*[image] [image]*

• Documentation

• FR
Français (FR)

• Anglais (EN)
Se connecter

• HAL science ouverte

• Recherche
Loading...

## Recherche avancée

Information de documents

Titres

○ Titres

○ Sous-titre

○ Titre de l'ouvrage

○ Titre du volume (Série)

○ Champ de recherche par défaut (multicritères) + texte intégral des PDF

○ Résumé

○ Texte intégral indexé des documents PDF

○ Mots-clés

○ Type de document

○ Sous-type de document

○ Tous les identifiants du document

○ Identifiant HAL du dépôt

○ Langue du document (texte)

○ Pays (Texte)

○ Ville

○ À paraître (true ou false)

Ajouter

Auteur
# A Hypergraph Model and Associated Optimization Strategies for Path Length-Driven Netlist Partitioning

Julien Rodriguez, François Galea, François Pellegrini, Lilia Zaourar

► To cite this version:

Julien Rodriguez, François Galea, François Pellegrini, Lilia Zaourar. A Hypergraph Model and Associated Optimization Strategies for Path Length-Driven Netlist Partitioning. ICCS 2023 - 23rd International Conference on Computational Science, Jul 2023, Prague, Czech Republic. pp.652-660, 10.1007/978-3-031-36024-4_50. hal-04379716

HAL Id: hal-04379716

https://hal.science/hal-04379716v1

Submitted on 15 Jan 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
## Auteur (multicritères)

○ Auteur (multicritères)

○ Auteur : Nom complet

○ Auteur : Nom de famille

○ Auteur : Prénom

○ Auteur : Complément de nom, deuxième prénom

○ Auteur : Organisme payeur

○ Auteur : IdHal (chaîne de caractères)

○ Auteur : Fonction

○ Auteur : personID (entier)

○ Auteur : Identifiant de l'organisme payeur

○ Auteur : Identifiant de la structure

○ Directeur de thèse

○ Éditeur

○ Éditeur scientifique

○ Éditeur de la série

## Ajouter

### Structure

### Structure (multicritères)

○ Structure (multicritères)

○ Structure : Acronyme

○ Structure : Nom

○ Structure : Code

○ Structure : Pays

○ Structure : Type

○ Structure : État dans le référentiel

○ Structure : Identifiant HAL de la structure

○ Structure/équipe de recherche : Pays

○ Structure/regroupement d'équipes : Pays

○ Structure/laboratoire : Pays

○ Structure/regroupement de laboratoires : Pays

○ Structure/institution : Pays

○ Structure/regroupement d'institutions : Pays

## Ajouter

## Autres
A Hypergraph
Model and Associated Optimization Strategies
for Path Length-Driven Netlist Partitioning

Julien Rodriguez¹,², François Galea¹, François Pellegrini², and Lilia Zaourar¹

¹ Université Paris-Saclay, CEA List, F-91120, Palaiseau, France
name.surname@cea.fr

² Université de Bordeaux & INRIA, F-33405, Talence, France
francois.pellegrini@u-bordeaux.fr

**Abstract.** Prototyping large circuits on multi-FPGA platforms requires to partition the circuits into sub-circuits, each to be mapped in a given signle FPGA. While most existing partitioning algorithms focus on minimizing cut size, the main issue is not to map long paths across multiple FPGAs, as it may cause an increase in critical path length. To address this problem, we propose a new hypergraph model, for which we design algorithms for initial partitioning and partition refinement. We integrate these algorithm in a multilevel framework, combined with existing min-cut solvers, to tackle simultaneously both path length and cut size objectives. We observe a significant reduction in critical path degradation, by 12%-40%, at the cost of a moderate increase in cut size, compared to path-agnostic min-cut methods.

**Keywords:** hypergraph partitioning · critical path · VLSI · FPGA · fast prototyping.

# 1 Introduction

The typical hardware design flow comprises several steps, such as prototyping, verification, floor planning, placement and routing, possibly on very large logic circuits. The methods which perform these steps often take advantage of *netlist partitioning*, which enables divide-and-conquer approaches to separate circuits into parts of smaller size that are easier to handle. Thus, reduce as much as possible the work on the global circuit. This study focuses on netlist partitioning for prototyping on multi-FPGA platforms, for circuits that do not fit into a single FPGA. In this case, the circuit is divided into several parts, one for each FPGA. Valid partitions must respect capacity constraints on each FPGA and their interconnections. In addition, it should mitigate a possible increase in the signal propagation delay of the longest combinatorial path, known as the *critical path*. Indeed, in synchronous circuits, critical path length determines the maximum frequency at which the circuit may operate. mapping long paths across several FPGAs is likely to degrade the critical path. During the last 30 years, several hypergraph partitioning tools have been developed [4, 9, 14]. These tools use a multi-level framework, that consists of three phases: *coarsening*, *initial partitioning*,
Champ de recherche par défaut (multicritères)

○ <u>Champ de recherche par défaut (multicritères)</u>

○

○ <u>Revues (multicritères)</u>

○ <u>Revue : Éditeur</u>

○ <u>Revue : Titre abrégé</u>

○ <u>Revue : Titre</u>

○ <u>Revue : Identifiant interne</u>

○ <u>Revue : Date de début de publication</u>

○ <u>Revue : ISSN électronique</u>

○ <u>Revue : ISSN</u>

○ <u>Revue : Éditeur</u>

○ <u>Revue : Couleur dans SHERPA/RoMEO</u>

○ <u>Revue : État dans le référentiel</u>

○

○ <u>Colloque (multicritères)</u>

○ <u>Colloque : Titre</u>

○ <u>Colloque : Organisateur</u>

○ <u>Colloque : date de début (Année)</u>

○ <u>Colloque : date de fin (Année)</u>

○ <u>Conférence invitée (oui/non)</u>

○

○ <u>Projets ANR (multicritères)</u>

○ <u>Projet ANR : Acronyme</u>

○ <u>Projet ANR : Acronyme du programme</u>

○ <u>Projet ANR : Code décision (référence)</u>

○ <u>Projet ANR : Nom</u>

○ <u>Projet ANR : Identifiant interne</u>

○ <u>Projet ANR : État dans le référentiel</u>

○

○ <u>Projets européens (multicritères)</u>

○ <u>Projet européen : Acronyme</u>

○ <u>Projet européen : Identifiant de l'appel à projet</u>

○ <u>Projet européen : Référence</u>

○ <u>Projet européen : Nom</u>

○ <u>Projet européen : Date de fin</u>

○ <u>Projet européen : Financement</u>

○ <u>Projet européen : Date de début</u>

○ <u>Projet européen : État dans le référentiel</u>
and *refinement*. The coarsening phase recursively uses a clustering method to transform the hypergraph into smaller ones, that possess the same topological properties. Then, an initial partitioning is computed on the smallest coarsened hypergraph. Finally, for each coarsening level, the solution for the coarser level is prolonged to the finer level, and then refined using a local refinement algorithm. A survey on hypergraph partitioning has been recently issued [5]. Common metrics to measure the quality of hypergraph partitions are $f_c$, which sums the number of cut hyperedges, and $f_λ$, which sums the number of connected parts, minus one, for each hyperedge, and which represents the amount of information that needs to be transferred across parts. However, all of these tools, while commonly used in production chains, have not been designed to minimize the critical path length, as shown in [2]. This is why several authors proposed pre- and/or post-processing steps to reduce the degradation of cut paths [2,12]. However, the main objective addressed by these works is to reduce the cut along critical paths as much as possible, not considering the critical path's degradation resulting from subsequent mapping onto a non-fully connected target topology. This paper proposes a cost function to minimize path cost degradation during partitioning, based on a modeling of circuits as *red-black hypergraphs*. We also propose a weighting scheme to drive *min-cut* tools as well as a partitioning scheme comprising several algorithms. It includes an adaptation of a refinement algorithm that aims at preventing cuts across the longest paths while still trying to minimize cut size. The remainder of the paper is organized as follows. Section 2 presents the notations, definitions, and previous work on time-driven partitioning. Section 3 presents our approach, relying on a new initial partitioning algorithm and an extension of the well-known Fiduccia–Mattheyses (FM) algorithm [8] to minimize path cost. Simulation and results are presented in Section 4. We conclude in Section 5.

# 2 Preliminaries

## 2.1 Notations and Definitions

Oriented hypergraphs are a generalization of oriented graphs in which the notion of arc is extended to that of hyperarc, which can connect one or more source vertices to one or more sink vertices. In our context, we consider only hyperarcs that comprise a single source vertex. Let $\mathcal{H} \stackrel{\text{def}}{=} (\mathcal{V}, \mathcal{A}, \mathcal{W}_v, \mathcal{W}_a)$ be a directed hypergraph, defined by a set of vertices $\mathcal{V}$ and a set of hyperarcs $\mathcal{A}$, with a vertex weight function $\mathcal{W}_v : \mathcal{V} \to \mathbb{R}^+$ and a hyperarc weight function $\mathcal{W}_a : \mathcal{A} \to \mathbb{R}^+$. Every hyperarc $a \in \mathcal{A}$ is a subset of vertex set $\mathcal{V}$: $a \subseteq \mathcal{V}$. Let $s^+(a)$ be the source vertex set of hyperarc $a$, and $s^-(a)$ its sink (destination) vertex set. We consider here that each hyperarc has a single source, so $\forall a, |s^+(a)|=1$. As hyperarcs connect vertices, let $\Gamma(v)$ be the set of neighbor vertices of vertex $v$, and $\Gamma^-(v) \subseteq \Gamma(v)$ and $\Gamma^+(v) \subseteq \Gamma(v)$ the sets of its inbound and outbound neighbors, respectively. In the model we propose, hypergraphs that model circuits are represented as sets of interconnected Directed Acyclic Hypergraphs (DAHs), associated with a red-black vertex coloring scheme. Red vertices correspond to I/O (Input/Output) ports and registers, and black vertices to combinatorial components. Let $\mathcal{V}^R \subset \mathcal{V}$ and $\mathcal{V}^B \subset \mathcal{V}$ be the red and black vertex subsets of $\mathcal{V}$, such that $\mathcal{V}^R \cap \mathcal{V}^B = \emptyset$
○ Projet européen : Identifiant interne

○

○ Date de production : année

○ Date de mise en ligne : année

○ Date de publication : année

○ Date d'écriture : année

○ Date de modification du dépôt : année

○ Date de dépôt : année

○ Date de publication électronique : année

○

○ Collection HAL (multicritères)

○ Collection HAL : catégorie

○ Collection HAL : Code

○ Collection HAL : Nom

○ Collection HAL : Identifiant interne

○

○ Identifiant interne du contributeur/déposant

○ Nom complet du contributeur/déposant

○

○ Domaines

○ Domaine primaire

○ Domaine racine

○ Sous-domaine niveau 1

○ Sous-domaine niveau 2

○ Sous-domaine niveau 3

○

○ Statut du document

○ Version du document

○ Type de dépôt

○ Type de document

○ ISBN

○ Numéro - référence

○ Identifiant DOI

○

○ Classification

○ Audience

○ Vulgarisation

○ Comité de lecture - texte (oui ou non)

○ Actes de colloque

○ Référence interne
and $V^R \cup V^B = V$. A hypergraph or sub-hypergraph $\mathcal{H}$ is a DAH iff its red vertices $v_R \in V^R$ are either only sources or sinks ($i.e., \Gamma^-(v_R)=\emptyset$ or $\Gamma^+(v_R)=\emptyset$), and no cycle path connects a vertex to itself. Using this definition, we can represent circuit hypergraphs as *red-black hypergraphs*, which are sets of DAHs that share their red vertices. Let $\mathbf{H}(\mathbf{V}, \mathbf{A}) \stackrel{\text{def}}{=} \{\mathcal{H}_i, i \in \{1 \dots n\}\}$ be a *red-black hypergraph*, such that every $\mathcal{H}_i$ is a DAH and an edge-induced sub-hypergraph of $\mathbf{H}$. In our model, the paths in $\mathbf{H}$ to consider when addressing the objective of minimizing *path-cost* degradation during partitioning are only the paths interconnecting red vertices, as these red-red paths represent register-to-register paths. Since only red vertices are shared between DAHs in $\mathbf{H}$, any red-red path only exists within a single DAH and can never span across several DAHs.

Let us define **P** as the set of red-red paths in **H**. From these paths and a function $d_{max}(u, v)$ which computes the maximum distance between vertices u and v of some DAH $\mathcal{H}$, we can now define the longest path distance for $\mathcal{H}$ as: $d_{max}(\mathcal{H}) \stackrel{\text{def}}{=} \max(d_{max}(u, v)|u, v \in \mathcal{H})$ and, by extension, for **H**, as: $d_{max}(\mathbf{H}) \stackrel{\text{def}}{=} \max(d_{max}(\mathbf{H})|\mathcal{H} \in \mathbf{H})$.

A k-partition $\Pi$ of $\mathbf{H}$ is a splitting of $\mathbf{V}$ into k vertex subsets $\pi_1, \dots, \pi_k$, called parts, such that: (i) all parts $\pi_i$, given a capacity bound $C_i$, respect the capacity constraint: $\sum_{v \in \pi_i} W_v(v) \le C_i$; (ii) all parts are pairwise disjoint: $\forall i \ne j, \pi_i \cap \pi_j = \emptyset$; (iii) the union of all parts is equal to $\mathbf{V}$: $\bigcup_i \pi_i = \mathbf{V}$. For a given partition $\Pi$ of $\mathbf{H}$, the connectivity $\lambda_{\Pi}(a)$ of some hyperarc $a \in \mathcal{A}$ is the number of parts connected by $a$. If $\lambda_{\Pi}(a) > 1$, then $a$ is said to be cut; otherwise it is entirely contained within a single part and is not cut. The cut of partition $\Pi$ is the set $\omega(\Pi)$ of cut hyperarcs, such as $\omega(\Pi) \stackrel{\text{def}}{=} \{a \in \mathcal{A}, \lambda_{\Pi}(a) > 1\}$. The cut size is defined as $f_c \stackrel{\text{def}}{=} \sum_{a \in \omega(\Pi)} W_a(a)$. The connectivity-minus-one cost function $f_{\lambda}$ of some partitioned hypergraph $\mathbf{H}^{\Pi}$ can then be defined as: $f_{\lambda} = \sum_{a \in \mathcal{A}} (\lambda_{\Pi}(a) - 1)$. Consequently, in our model, the distance between two vertices u and v may increase during partitioning due to the additional cost of routing paths between two (or more) parts. Let $D_{ij}$ be the penalty associated with parts i and j such that if u is in part i and v is in part j, then: $d_{max}^{\Pi}(u,v) \ge d_{max}(u,v) + D_{ij}$. The objective function $f_p$ can therefore be defined as the minimization of the longest path of $\mathbf{H}$ subject to partition $\Pi$: $f_p = \min d_{max}(\mathbf{H}^{\Pi})$.

## 2.2 Related Work

Many previous works exploit existing *min-cut* partitioning tools, used as black boxes, and try to account for additional constraints. For instance, [2] presents a multi-objective approach based on HMETIS. In [1] is proposed a pre-processing coupled with a recursive bi-partitioning algorithm using HMETIS. They use path length values a hyperarc weights, to channel the partitioner towards minimizing path cost. Since path length values can change as the result of a bi-partitioning step, hyperarc weights are reevaluated after each of them to identify critical hyperarcs. Reference [6] compares a classic method using HMETIS for partitioning, followed by a placement algorithm, with a derived approach consisting in placing and routing during the partitioning step. More recently, [10] performs some pre- and post-processing on the hypergraph to capture the critical path minimization objective within the cut-size metric, using HMETIS as a partitioning tool. However, minimizing cut size is often not the most
○ Financement

○ Collaborations

Ajouter

Lancer la recherche

Recherche experte (SolR)

Recherche experte (SolR)

Lancer la recherche
Vers la recherche avancée

• Déposer

X

X

X

Loading...

X

Le document que vous demandez est en access restreint
jusqu'au 2024-07-20 !

Revenir a la notice

Retourner à l'accueil

[image]

[image]

[image]

[image]

Contact

• Support

Ressources

• Documentation

• FAQ

• API
relevant objective, and biasing *min-cut* cost functions to take *path-cost* minimization into account does not allow to handle properly platform topologies.

# 3 Contributions

Our first contribution consists of two initial partitioning algorithms, called DBFS and DDFS. They are based on breadth-first-search and depth-first-search methods, respectively. Both are driven by *vertex criticality*, i.e., the length of the longest path traversing a vertex. These algorithms are combined with some cut minimization tools to achieve both objectives of preserving critical paths and minimizing the cut. Our second contribution consists of an extension of the FM heuristic [8], called DKFM. It aims to perform moves that minimize the cost function $f_p$, taking into account the target topology. The objective is to use DKFM as a post-processing cut minimization tool, for instance as a refinement method within a multilevel framework.

<figure><img src="image_2.png" /><figcaption>Fig. 1: A hint on DDFS vs. DBFS. All hatched nodes will be placed in the same part. DBFS avoids multiple cuts along paths within a DAH, while DDFS does not (see the red circle in the DDFS example). However, if a critical path starts in *DAH*₂ from a sink of *DAH*₁, DBFS can produce a cut along this critical path, while DDFS cannot (see the red circle in the DBFS example).</figcaption></figure>

## 3.1 Initial Partitioning Based on Breadth-First Search Driven by Vertex Criticality (DBFS)

This first initial partitioning algorithm is based on an extended search along the vertices of H, driven by criticality. It groups neighboring vertices of each vertex v according to their criticality, to avoid multiple cuts along a long path. In our context, the multiple-cut constraint is also important because we need to avoid cutting the same path multiple times. Indeed, the cutting cost $D_{ij}$ is often larger than the path length. However, many paths can be shorter than the longest path before partitioning. Therefore, our algorithm considers the criticality of each vertex v in addition to the criticality of its neighbors. To select vertices to consider, we use their in-degree value, decremented for all outgoing neighbors of v when visiting v. This gives us a topology-driven hypergraph traversal, considering vertex criticality. This algorithm allows us to perform a walk along the topological order in the current DAH, by selecting, at each step, a neighbor of maximum criticality. This choice allows us to favor the grouping, within the same part, of neighboring vertices with high criticality.
• OAI-PMH

• AuréHAL

## Informations

• À propos

• Données personnelles

• Mentions légales

• Accessibilité

• Conformité RGAA

## Questions juridiques

• Je publie, quels sont mes droits ?

• Loi pour une République numérique

• Stratégie de non-cession des droits

• SHERPA/RoMEO

## Portails

• Portails institutionnels

• HAL

• HAL SHS

• HAL Thèses

• MédiHAL

## CCSD

• CCSD

• Episciences

• Sciencesconf
As long as the size constraint is respected, each selected vertex will be placed in the same part. An example can be found in Figure 1.

## 3.2 Initial Partitioning Based on Depth-First Search and Vertex Criticality (DDFS)

This second initial partitioning method performs a depth-first traversal driven by the criticality of the vertices. The main difference with the previous method is that all vertices will be inserted in the same priority queue, regardless of whether they are red or black. It enables a more compact visit order concerning the criticality value, but does not consider the topological structure of DAHs in **H**. The main idea behind this method is to be able to pack interconnected critical paths of several DAHs in the traversal order. If the topology allows for it, the most critical neighboring paths will be placed in the same part, as long as the size constraint is respected. An example can be found in Figure 1. However, DDFS may induce cuts within the DAHs and a possible path cost degradation for paths of smaller criticality. The relative efficiency of DBFS and DDFS is likely to vary, depending on circuit topologies and the distributions of path lengths.

## 3.3 FM-Based Local Optimization Heuristic (DKFM)

A commonly used heuristic in partitioning tools is the algorithm proposed by Fiduccia and Mattheyses (FM) [8]. It is based on *local search* to move vertices across parts so as to reduce the cut of balanced hypergraph bipartitions. FM computes a move gain for each vertex and performs a single move at each step.

We propose an extension of this algorithm to minimize critical path degradation during partitioning. Let $Π$ be a partition of **H**; the gain function for some vertex $v$ and some candidate partition $Π'$ in which $v$ may be moved to part $π_k$ is defined as:
$$gain(Π, Π', H) \stackrel{\text{def}}{=} d_{max}^{Π}(H) - d_{max}^{Π'}(H).$$

# 4 Experimental Results

## 4.1 Methodology

The hypergraphs of our benchmark are taken from the Titan23 [11] and ITC99 [7] benchmarks, and Chipyard [3]. We also defined two target topologies composed of four elements. Test Architecture 1 connects its four FPGAs as a cycle $π_0, π_1, π_2, π_3$, while Architecture 2 is a chain $π_0, π_1, π_2, π_3$. In order to evaluate the DBFS and DDFS algorithms, we first generated an initial partition and then ran KKAHYPAR to refine it, using the objective function $f_λ$. To test the DKFM refinement algorithm, we first ran PATOH-S, KHMETIS, and KKAHYPAR on the weighted hypergraph instances xxx_w, with our weighting scheme driven by vertex-hyperarc criticality. Then, we applied our DKFM algorithm as post-processing to these outputs, to study the path-cost improvement and possible degradation of the connectivity-minus-one metric induced by our refinement pass. We chose KHMETIS over HMETIS, used in previous works, because we get better results in the majority of cases for both target
topologies. We select PATOH in its "speedy" (S) version to see whether it could
produce acceptable solutions in combination with DKFM, because computation time
is a critical aspect of industrial-size circuit prototyping.

## 4.2 Initial Partitioning Algorithms

<figure><img src="image_3.png" /><figcaption>Fig. 2: Comparison of $f_p$ on Architecture 1 (a) and Architecture 2 (b).</figcaption></figure>

Figures 2a and 2b evidence that in many cases, initial partitioning algorithms DBFS and DDFS, combined with our weighting scheme, can influence a cut minimization partitioning tool to improve path cost. However, for some instances (b17, OneCore), the algorithms perturb the cut minimization tools and produce worse results. Combined with a cut minimization tool, these two algorithms yield an average improvement in 18% (DBFS) and 45% (DDFS) of the instances when mapping onto Architecture 1, and an average improvement in 36% of the instances on Architecture 2, for both algorithms. Compared to the cut minimization approach, DBFS improves the path cost metric by 8% and 7% on the two architectures, respectively, while DBFS improves path cost by 7% and 17%, respectively. Moreover, in many instances, the produced path cost is equal to the lowest possible cost, and it is impossible to improve it further. It shows that both algorithms indeed prevented critical paths from being cut. We already see a gain at this scale, which is encouraging for testing these methods on more significant cases. The quality of the partitions produced by the two algorithms varies, depending on the instances. We suppose this somewhat reflects the topological properties of the instances (e.g., whether the black vertices are heavily interconnected at each level). Further analysis are required to determine relevant criteria. Our two algorithms differ in the way vertices are visited: DDFS (depth-first) is more likely to cluster long paths in the same part, while DBFS (breadth-first) is more likely to cluster together vertices on the same level with respect to source red vertices. We assume that these algorithms succeed in preventing the same path from being cut multiple times, by packing together the neighborhood of black vertices within DAHs. It allows them to produce results that are topologically compatible with the different hardware topologies. Notably, DBFS is adapted to linear (streamlined) hardware topologies, where vertices belonging to the same levels of computation must be packed together.
instances and their underlying topologies. DKFM results show an average improvement in critical path length ranging between 12% and 40%, compared to the initial min-cut solutions. These algorithms seem to be a good approach for the prototyping of circuits on a multi-FPGA platform. However, these methods can degrade cut size by a factor from 1.2 up to 5.0. At this stage, only the DKFM refinement algorithm takes into account the topology of the target hardware and correctly manages outliers. Hence, it may not be easy to improve incrementally and locally on results provided by the architecture-unaware algorithms DBFS and DDFS. It would be interesting to work on the placement of vertices according to the target topology from the initial partitioning phase, as SCOTCH [13] does for unoriented graphs.

## References

1. Ababei, C., Bazargan, K.: Timing minimization by statistical timing hMetis-based partitioning. In: 16th International Conference on VLSI Design, 2003. Proceedings.

2. Ababei, C., Navaratnasothie, S., Bazargan, K., Karypis, G.: Multi-objective circuit partitioning for cutsize and path-based delay minimization. In: ICCAD 2002.

3. Amid, A., Biancolin, D., Gonzalez, A., Grubb, D., Karandikar, S., Liew, H., Magyar, A., Mao, H., Ou, A., Pemberton, N., Rigge, P., Schmidt, C., Wright, J., Zhao, J., Shao, Y.S., Asanović, K., Nikolić, B.: Chipyard: Integrated design, simulation, and implementation framework for custom socs. IEEE Micro 40(4), 10–21 (2020)

4. Çatalyürek, Ü., Aykanat, C.: PaToH. Springer US, Boston, MA (2011)

5. Çatalyürek, U., Devine, K., Faraj, M., Gottesbüren, L., Heuer, T., Meyerhenke, H., Sanders, P., Schlag, S., Schulz, C., Seemaier, D., Wagner, D.: More recent advances in (hyper)graph partitioning. ACM Comput. Surv. 55(12) (mar 2023)

6. Chen, M.H., Chang, Y.W., Wang, J.J.: Performance-Driven Simultaneous Partitioning and Routing for Multi-FPGA Systems. In: 2021 58th ACM/IEEE DAC (2021)

7. Corno, F., Reorda, M., Squillero, G.: RT-level ITC'99 benchmarks and first ATPG results. IEEE Design & Test of Computers 17(3), 44–53 (2000)

8. Fiduccia, C., Mattheyses, R.: A Linear-Time Heuristic for Improving Network Partitions. In: 19th DAC (1982). https://doi.org/10.1109/DAC.1982.1585498

9. Karypis, G., Kumar, V.: Hmetis: a hypergraph partitioning package. ACM Transactions on Architecture and Code Optimization (1998)

10. Liou, S.H., Liu, S., Sun, R., Chen, H.M.: Timing Driven Partition for Multi-FPGA Systems with TDM Awareness. Ass. Comp. Mach., New York, NY, USA (2020)

11. Murray, K.E., Whitty, S., Liu, S., Luu, J., Betz, V.: Timing-Driven Titan: Enabling Large Benchmarks and Exploring the Gap between Academic and Commercial CAD. ACM Trans. Reconf. Technol. Syst. 8(2) (mar 2015)

12. Ou, S.L., Pedram, M.: Timing-driven partitioning using iterative quadratic programming

13. Pellegrini, F., Roman, J.: SCOTCH: A Software Package for Static Mapping by Dual Recursive Bipartitioning of Process and Architecture Graphs. In: HPCN Europe (1996)

14. Schlag, S.: High-Quality Hypergraph Partitioning. Ph.D. thesis, Karlsruhe Institute of Technology, Germany (2020)