NDLI: The Extended Partitioning Problem: Hardware/Software Mapping, Scheduling, and Implementation-bin Selection

Please wait, while we are loading the content...

The Extended Partitioning Problem: Hardware/Software Mapping, Scheduling, and Implementation-bin Selection

Content Provider	Springer Nature Link
Author	Kalavade, Asawaree Lee, Edward A.
Copyright Year	1997
Abstract	In system-level design, applications are represented as task graphs where tasks (called nodes) have moderate to large granularity and each node has several implementation options differing in area and execution time. We define the extended partitioning problem as the joint determination of the mapping (hardware or software), the implementation option (called implementation bin), as well as the schedule, for each node, so that the overall area allocated to nodes in hardware is minimum and a deadline constraint is met. This problem is considerably harder (and richer) than the traditional binary partitioning problem that determines just the best mapping and schedule. Both binary and extended partitioning problems are constrained optimization problems and are NP-hard.We first present an efficient(O(N 2)) heuristic, called GCLP, to solve the binary partitioning problem. The heuristic reduces the greediness associated with traditional list-scheduling algorithms by formulating a global measure, called global criticality (GC). The GC measure also permits an adaptive selection of the optimization objective at each step of the algorithm; since the optimization problem is constrained by a deadline, either area or time is optimized at a given step based on the value of GC. The selected objective is used to determine the mapping of nodes that are “normal”, i.e. nodes that do not exhibit affinity for a particular mapping. To account for nodes that are not “normal”, we define “extremities” and “repellers”. Extremities consume disproportionate amounts of resources in hardware and software. Repellers are inherently unsuitable to either hardware or software based on certain structural properties. The mapping of extremities and repellers is determined jointly by GC and their local preference.We then present an efficient ( O(N 3 + N 2 B), for N nodes and B bins per node) heuristic for extended partitioning, called MIBS, that alternately uses GCLP and an implementation-bin selection procedure. The implementation-bin selection procedure chooses, for a node with already determined mapping, an implementation bin that maximizes the area-reduction gradient of as-yet unmapped nodes. Solutions generated by both heuristics are shown to be reasonably close to optimal. Extended partitioning generates considerably smaller overall hardware as compared to binary partitioning.
Starting Page	125
Ending Page	163
Page Count	39
File Format	PDF
ISSN	09295585
Journal	Design Automation for Embedded Systems
Volume Number	2
Issue Number	2
e-ISSN	15728080
Language	English
Publisher	Kluwer Academic Publishers
Publisher Date	1997-01-01
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Special Purpose and Application-Based Systems Computer-Aided Engineering (CAD, CAE) and Design Electronic and Computer Engineering
Content Type	Text
Resource Type	Article
Subject	Software Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Editorial: Special Issue on Hardware/Software Partitioning

An Iterative Algorithm for Hardware-Software Partitioning, Hardware Design Space Exploration and Scheduling

Hardware-Software Partitioning for Real-Time Embedded Systems

Algorithmic aspects for functional partitioning and scheduling in hardware/software co-design

Extending the Kernighan/Lin Heuristic for Hardware and Software Functional Partitioning

An Algorithm for Hardware/Software Partitioning Using Mixed Integer Linear Programming

Comparing Three Heuristic Search Methods for Functional Partitioning in Hardware–Software Codesign

A method for partitioning applications in hybrid reconfigurable architectures

System Level Hardware/Software Partitioning Based on Simulated Annealing and Tabu Search

The Extended Partitioning Problem: Hardware/Software Mapping, Scheduling, and Implementation-bin Selection

Similar Documents

Editorial: Special Issue on Hardware/Software Partitioning

An Iterative Algorithm for Hardware-Software Partitioning, Hardware Design Space Exploration and Scheduling

Hardware-Software Partitioning for Real-Time Embedded Systems

Algorithmic aspects for functional partitioning and scheduling in hardware/software co-design

Extending the Kernighan/Lin Heuristic for Hardware and Software Functional Partitioning

An Algorithm for Hardware/Software Partitioning Using Mixed Integer Linear Programming

Comparing Three Heuristic Search Methods for Functional Partitioning in Hardware–Software Codesign

A method for partitioning applications in hybrid reconfigurable architectures

System Level Hardware/Software Partitioning Based on Simulated Annealing and Tabu Search

The Extended Partitioning Problem: Hardware/Software Mapping, Scheduling, and Implementation-bin Selection