System architecture synthesis and exploration for multiple functional specifications

• US 7,031,887 B2
• Filed: 07/31/2001
• Issued: 04/18/2006
• Est. Priority Date: 07/31/2001
• Status: Expired due to Fees

• Current Assignee: Agilent Technologies, Inc.
• Original Assignee: Agilent Technologies, Inc.
• Inventors: Jain, Rajiv, Su, Alan Peisheng, Biswas, Chaitali
• Primary Examiner(s): Rodriquez, Paul L.
• Assistant Examiner(s): GUILL, RUSSELL L
• Application Number:
  US09/918,734
• Publication Number:
  US 20030028578A1
• Time in Patent Office: 1,722 Days
• Field of Search: 703/1, 716/7
• US Class Current: 703/1
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

A method is provided for exploring alternative architectures for partitioning computer system resources to execute multiple task specifications. An initial master task graph is formed from the multiple task specifications, the initial master task graph including at least one hierarchical task with pointers to either AND sub-task graphs or XOR sub-task graphs. The initial master task graph is processed to provide a selected number of final master task graphs, each of the final master task graphs comprising a list of AND task graphs. A family of architectures is generated for each of the final master task graphs, each of the architectures generated for a given master task graph being capable of executing every AND task graph included therein. The degree of resemblance in composition, functional capability or performance resulting between architectures from different master task graphs is a function of the correlation between the contents of these master task graphs and not of concern to the user of the aforementioned method.

Claims

1. A method for generating computer system level architectures that are capable of executing multiple functional specifications, given a set of physical resources, and subject to a set of design constraints, the method comprising:

forming an initial master task graph from said multiple specifications, said initial master task graph including at least one hierarchical task having pointers to a plurality of sub-task graphs, wherein an XOR relationship exists between at least two of the plurality of sub-task graphs;

processing said initial master task graph to provide a selected number of final master task graphs, each of said final master task graphs comprising a list of AND task graphs;

generating a family of architectures for each of said final master task graphs, each of the architectures generated for a given final master task graph being capable of executing every AND task graph included in the list for the given final master task graph; and

exploring each of said generated architectures for use in executing said multiple specifications.

2. The method of claim 1 wherein:

said initial master task graph includes a first hierarchical task having an AND attribute, and a second hierarchical task having an XOR attribute.

3. The method of claim 2 wherein said processing step comprises:

resolving said initial master task graph into sets of AND task graphs on the basis of respective sub-task graphs associated with said first hierarchical task; and

resolving said sets of AND task graphs into said final master task graphs.

4. The method of claim 1 wherein:

said given final master task graph is applied to an architecture synthesis engine to generate a family of architectures therefor.

5. The method of claim 1 wherein said exploring step comprises:

placing each of the architectures generated for said given final master task graph into a pool; and

retaining a particular architecture in said pool only if said particular architecture can execute each AND task graph of said given final master task graph in accordance with a prespecified time schedule.

6. The method of claim 1 wherein:

a generated architecture is disposed to execute specified multiple tasks from said multiple specifications on a single component that is selected from said set of resources.

7. The method of claim 1 wherein:

a generated architecture is disposed to execute specified multiple tasks from said multiple specifications on the same type, but different instances, of a component that is selected from said set of resources.

8. An article of manufacture for generating system level architectures that are capable of executing multiple functional specifications, given a set of physical resources, and subject to a set of design constraints, said article of manufacture comprising:

a computer readable medium;

a plurality of instructions wherein at least a portion of said plurality of instructions are storable in said computer readable medium, and further wherein said plurality of instructions are configured to cause a processor to;

form an initial master task graph from said multiple specifications, said initial master task graph including at least one hierarchical task having pointers to a plurality of sub-task graphs, wherein an XOR relationship exists between at least two of the plurality of sub-task graphs;

process said initial master task graph to provide a selected number of final master task graphs, each of said final master task graphs comprising a list of AND task graphs;

generate family of architectures for each of said final master task graphs, each of the architectures generated for a given final master task graph being capable of executing every AND task graph included in the list for the given final master task graph; and

explore each of said generated architectures for use in executing said multiple specifications.

9. The article of manufacture of claim 8 wherein:

said initial master task graph includes a first hierarchical task having an AND attribute, and a second hierarchical task having an XOR attribute.

10. The article of manufacture of claim 9 wherein said processing step comprises;

resolving said initial master task graph into sets of AND task graphs on the basis of respective sub-task graphs associated with said first hierarchical task; and

resolving said sets of AND task graphs into said final master task graphs.

11. The article of manufacture of claim 8 wherein:

said given final master task graph is applied to an architecture synthesis engine to generate a family of architectures therefor.

12. The article of manufacture of claim 8 wherein said exploring step comprises:

placing each of the architectures generated for said given final master task graph into a pool; and

retaining a particular architecture in said pool only if said particular architecture can execute each AND task graph of said given final master task graph in accordance with a prespecified time schedule.

13. The article of manufacture of claim 8 wherein:

a generated architecture is disposed to execute specified multiple tasks from said multiple specifications on a single component that is selected from said set of resources.

14. The article of manufacture of claim 8 wherein:

a generated architecture is disposed to execute specified multiple tasks from said multiple specifications on the same type, but different instances, of a component that is selected from said set of resources.