Resource allocation in rooted trees for VLSI applications. (3rd June 2019)

• Record Type: Journal Article
• Authors: Wimer, Uri; Wimer, Shmuel
• Is Part Of: Optimization. Volume 68:Number 6(2019)
• Page Start: 1187
• Page End: 1201
• Publication Date: 2019-06-03
• Subjects: Resource allocation -- dynamic programming -- inverse 1-median -- circuit security -- delay distribution -- analog-to-digital converter; 90C27 -- 90C39; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2019.1576669
• Languages: English
• ISSNs: 0233-1934

Abstract

ABSTRACT: Several optimization problems of modifying the weight of vertices in rooted trees, some of which are special cases of the inverse 1-median problem, are solved. Such problems arise in Very Large Scale Integration (VLSI) design of hardware security circuits, circuit synchronization, and analog-to-digital converters. These problems require assigning costly hardware (demands) to the leaves of rooted trees. One common property of these problems is that a resource allocated to an internal node can be shared by the entire sub-tree emanated at the node. Two types of problems are studied here. (1) A tree node employs an addition operation and the demands at the leaves are obtained by summing the resources allocated to nodes along the root-to-leaf paths. A linear-time bottom-up algorithm is shown to minimize the total resources allocated to tree nodes. (2) A tree's node employs a multiplication operation and the demands at the leaves are obtained by multiplying the resources allocated to nodes along the root-to-leaf paths. A bottom-up dynamic programming algorithm is shown to minimize the total resources allocated to the tree's nodes. While the above problems are usually solved by design engineers heuristically, this paper offers optimal solutions that can be easily programmed in CAD tools.