Resource allocation in rooted trees for VLSI applications

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.