Fail-safe distributive processing method for producing a highest fitness cell placement for an integrated circuit chip

• US 5,815,403 A
• Filed: 04/19/1994
• Issued: 09/29/1998
• Est. Priority Date: 04/19/1994
• Status: Expired due to Term

• Current Assignee: Bell Semiconductor, LLC (Hilco Inc. (d/b/a Hilco Global))
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Scepanovic, Ranko, Koford, James S., Boyle, Douglas B., Rostoker, Michael D., Jones, Edwin R.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): MOHAMED, AYNI Y
• Application Number:
  US08/229,954
• Time in Patent Office: 1,624 Days
• Field of Search: 364/482-491, 364/578, 395/500
• US Class Current: 716/119
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06F 9/5033 considering data affinity

Abstract

A physical design automation system for producing a highest fitness cell placement for an integrated circuit chip includes a decomposition/recomposition processor for decomposing a cell placement optimization process into a plurality of tasks and recomposing the highest fitness cell placement from results of performing the tasks. A plurality of worker processors independently perform the tasks and produce results. A host processor distributively assigns the tasks to the worker processors in response to work requests received therefrom. Each worker processor sends a work request to the host processor after completing a task. The host processor maintains a list of unassigned tasks, assigned tasks and completed tasks, and revises the list to redesignate assigned tasks as unassigned tasks upon determining that the list includes no unassigned tasks and at least one assigned task, thus making the system immune to the failure of one or more processors.

Claims

1. A physical design automation system for producing a highest fitness cell placement for an integrated circuit chip, comprising:

a decomposition/recomposition processor for decomposing a cell placement optimization process into a plurality of tasks and recomposing said highest fitness cell placement from results of performing said tasks;

a plurality of worker processors for independently performing tasks and producing results; and

a host processor for distributively assigning said tasks to the worker processors in response to work requests received therefrom, wherein the host processor maintains a list of unassigned tasks, assigned tasks and completed tasks, and revises said list to redesignate assigned tasks as unassigned tasks in accordance with a predetermined criterion;

each worker processor sending a work request to the host processor after completing a task.

2. A system as in claim 1, in which said criterion comprises determining that said list includes no unassigned tasks and at least one assigned task.

3. A system as in claim 1, in which said criterion comprises determining that a predetermined length of time has elapsed after the host processor began assigning said tasks to the worker processors.

4. A distributive processing method for controlling a plurality of processors to independently perform tasks and produce results, comprising the steps of:

(a) distributively assigning said tasks to said processors in response to work requests received therefrom;

(b) causing each processor to produce a result and a work request after completing a task;

(c) maintaining a list of unassigned tasks, assigned tasks and completed tasks; and

(d) revising said list to redesignate assigned tasks as unassigned tasks in accordance with a predetermined criterion, in which said criterion comprises determining that said list includes no unassigned tasks and at least one assigned task.

5. A distributive processing method for controlling a plurality of processors to independently perform tasks and produce results, comprising the steps of:

(a) distributively assigning said tasks to said processors in response to work requests received therefrom;

(b) causing each processor to produce a result and a work request after completing a task;

(c) maintaining a list of unassigned tasks, assigned tasks and completed tasks; and

(d) revising said list to redesignate assigned tasks as unassigned tasks in accordance with a predetermined criterion, in which said criterion comprises determining that a predetermined length of time has elapsed after beginning step (a).

6. A method of producing a highest fitness cell placement for an integrated circuit chip, comprising the steps of:

(a) decomposing a cell placement optimization process into a plurality of tasks;

(b) distributively assigning said tasks to a plurality of processors in response to work requests received therefrom;

(c) causing each processor to produce a result and a work request after completing a task;

(d) recomposing said highest fitness cell placement from said results;

(e) maintaining a list of unassigned tasks, assigned tasks and completed tasks; and

(f) revising said list to redesignate assigned tasks as unassigned tasks in accordance with a predetermined criterion.

7. A method as in claim 6, in which said criterion in step (f) comprises determining that said list includes no unassigned tasks and at least one assigned task.

8. A method as in claim 6, in which said criterion in step (f) comprises determining that a predetermined length of time has elapsed after beginning step (b).