Browse Prior Art Database

Selecting Seed Vertices for Multiple Mappings Using the Automated Logic Mapping System

IP.com Disclosure Number: IPCOM000074233D
Original Publication Date: 1971-Apr-01
Included in the Prior Art Database: 2005-Feb-23
Document File: 3 page(s) / 45K

Publishing Venue

IBM

Related People

Mennone, A: AUTHOR [+2]

Abstract

The Automated Logic Mapping System is a set of computer programs which assigns blocks of a block graph to constrained subsets called modules. In the first step of the mapping process, a vertex generation program (VGP) assigns blocks to groups called vertices and in the second step, a vertex allocation program (VAP) allocates the vertices to modules to produce a mapping. These two programs are fully described in "An Algorithm for the Partitioning and Mapping of Computer Logic Blocks to Modules", R. L. Russo, P. H Oden and P. K. Wolff, Sr., RC 2815, IBM T. J. Watson Research Center, Yorktown Heights, N. Y., 10598.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Selecting Seed Vertices for Multiple Mappings Using the Automated Logic Mapping System

The Automated Logic Mapping System is a set of computer programs which assigns blocks of a block graph to constrained subsets called modules. In the first step of the mapping process, a vertex generation program (VGP) assigns blocks to groups called vertices and in the second step, a vertex allocation program (VAP) allocates the vertices to modules to produce a mapping. These two programs are fully described in "An Algorithm for the Partitioning and Mapping of Computer Logic Blocks to Modules", R. L. Russo, P. H Oden and P.
K. Wolff, Sr., RC 2815, IBM T. J. Watson Research Center, Yorktown Heights, N.
Y., 10598.

In VAP, the vertices initially allocated to the modules are called seeds because the modules grow around the seeds in the subsequent allocation phase. A VAP mapping (pass) consists of the initial vertex allocation phase (seeding) together with the subsequent vertex allocation phase in which VAP attempts to allocate every allocable vertex to a module. This publication describes an iterative procedure that uses either one of two independent heuristic seed selection algorithms by means of which multiple mappings are obtained. The seeding methods for the two algorithms are the same for pass one but they differ for subsequent passes.

For pass one, an allocable vertex with the largest number of net connections that fits on a module is used as a seed vertex on the module for the initial vertex allocation. VAP then completes the pass one mapping as described in the above referenced publication.

For subsequent passes it is desirable to find a set of seeds that are highly disjoint in the sense that the number of common nets is relatively low. A net that is common to n seeds requires n module pins at both the start and end of the subsequent allocation phase; it is desirable to keep the number of such committed pins small so that VAP will have as many free pins as possible with which to work. A module property provided by a VAP mapping is that the verticals allocated to each module are strongly connected; i.e., they share many nets. In fact, observing the order in which vertices are allocated to each module reveals that at some point in the allocation...