We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A link-elimination partitioning approach for application graph mapping in reconfigurable computing systems.
- Authors
Mohtavipour, Seyed Mehdi; Shahhoseini, Hadi Shahriar
- Abstract
Dynamic reconfiguration provides flexibility in the design and management of reconfigurable computing (RC) systems such that numerous applications would be mapped into limited resources simultaneously. As the mapping is a computationally intensive procedure in application compilation, a low-complex method is needed strongly for RC applications. In this paper, we propose a link-elimination partitioning approach for application graphs to reduce computations and reach an optimal solution faster as well. The link-elimination preprocessing step is performed by investigating the standard deviation of weights and removing lightweight links from the partitioning procedure. Based on the Laplacian matrix, a formulation method for detecting high-degree nodes as partition seeds has been generated. Moreover, a distance model for the region of implementation in resource graph has been introduced in this paper. In order to select among any rectangular shape of the resource graph, an average distance factor has been defined analytically. It has been proved that partitions with more connectivity must be implemented in a square-formed shape. Extensive experiments with random and benchmark graphs have been carried out to compare the proposed partitioning approach with the previous methods, and the results manifested that for fixed searching iterations, quality of solutions and time overhead have been improved 22% and 59%, respectively.
- Subjects
LAPLACIAN matrices; ADAPTIVE computing systems; RANDOM graphs; STANDARD deviations
- Publication
Journal of Supercomputing, 2020, Vol 76, Issue 1, p726
- ISSN
0920-8542
- Publication type
Article
- DOI
10.1007/s11227-019-03056-5