Scheduling non-integral simulation time for mixed-signal simulation

• US 6,961,689 B1
• Filed: 03/21/2000
• Issued: 11/01/2005
• Est. Priority Date: 03/21/2000
• Status: Expired due to Term

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synopsys Incorporated
• Inventors: Greenberg, Steven S.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Craig, Dwin M.
• Application Number:
  US09/531,350
• Time in Patent Office: 2,051 Days
• Field of Search: 703/17, 703/14, 703/4, 703/13, 703/16
• US Class Current: 703/17
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking

Abstract

In the simulation of an analog and mixed-signal analog-digital physical circuit, events are assigned scheduled times. The events are stored in buckets in a hash table, with the scheduled times of the events in each bucket associated with the bucket. The scheduled times are organized into a heap, with the earliest scheduled time at the root of the heap. The earliest scheduled time is removed from the heap, and the events in the associated bucket are performed. Performing the scheduled events can cause new events to be scheduled, and existing events to be de-scheduled. When all the events in the bucket associated with the earliest scheduled time are simulated, the remaining scheduled times are re-organized into a new heap, and the steps of removing the earliest scheduled time, performing the scheduled events, and re-organizing the remaining scheduled times are repeated.

Claims

1. A method for scheduling events occurring at scheduled times in a simulation model for modeling analog and mixed signal digital-analog physical circuits and systems in a digital computer, the method comprising:

assigning scheduled times to the events;

using a non-order preserving hash function based on the scheduled times of the events to store the events in buckets, each bucket containing at least one event;

wherein the buckets have no assigned order relative to one another;

associating the scheduled times assigned to the events in the buckets with the buckets;

organizing the scheduled times but not their events into a heap

wherein the heap comprises a binary tree of nodes that have a parent-child relationship, with a first node at one level higher than a second node being called a parent of the second node, and the second node being called a child of the first node, and each parent node having a smaller scheduled time than its two children;

removing an earliest scheduled time from the heap;

simulating the events in the bucket associated with the earliest scheduled time;

re-organizing the remaining scheduled times into a new heap; and

repeating the steps of removing a scheduled time, simulating the events, and re-organizing the remaining scheduled times until the heap is empty;

wherein the scheduled times are represented as real numbers.

2. A method according to claim 1, the method further comprising:

beginning the mixed-signal simulation;

determining the events from the mixed-signal simulation; and

determining the scheduled times for when the events are to occur.

3. A method according to claim 1, wherein simulating the events includes:

determining new events of the mixed-signal simulation;

determining the scheduled times for when the events are to occur; and

placing the new determined events into buckets using the hash function based on the scheduled times of the events.

4. A method according to claim 3, wherein placing the new determined events includes:

placing a first new determined event into a new bucket;

associating the scheduled time assigned to the first new determined event with the new bucket;

adding the new scheduled time associated with the new bucket to the heap; and

re-organizing the scheduled times into a new heap.

5. A method for scheduling events with associated scheduled times occurring at non-integral time intervals, the method comprising:

storing events in buckets according to their scheduled times;

wherein the buckets have no assigned order relative to one another; and

organizing the scheduled times into a structure, wherein the structure is constructed and arranged to allow easy location of an earliest scheduled time;

wherein the scheduled times are represented as real numbers.

6. A method according to claim 5, wherein storing events includes using a non-order preserving hash table to place the events into the buckets according to the scheduled times associated with the events.

7. A method according to claim 5, wherein each bucket is assigned a specific scheduled time and stores all events assigned that scheduled time.

8. A method according to claim 5, wherein the structure containing the scheduled times is organized as a heap.

9. A method according to claim 8, wherein the method further comprises:

removing a scheduled time from the heap; and

re-organizing the remaining scheduled times into a new heap.

10. A method according to claim 9, wherein removing a scheduled time includes performing the events in the bucket associated with the removed scheduled time.

11. A method according to claim 10, wherein performing the events includes checking to see if the bucket associated with the removed scheduled time is empty.

12. A method according to claim 5, wherein the method further comprises:

adding a new scheduled time to the heap; and

re-organizing the scheduled times into a new heap.

13. A method according to claim 5, wherein the method further comprises removing a de-scheduled event from a second bucket.

14. A computer-readable medium containing a program for scheduling events with associated scheduled times occurring at non-integral time intervals, the program comprising:

storage software to store events in buckets according to their scheduled times;

wherein the buckets have no assigned order relative to one another; and

organization software to organize the scheduled times into a structure, wherein the structure is constructed and arranged to allow easy location of an earliest scheduled time;

wherein the scheduled times are represented as real numbers.

15. A computer-readable medium containing a program according to claim 14, the storage software including hash software to use a non-order preserving hash table to place the events into the buckets according to the scheduled times associated with the events.

16. A system for scheduling events with associated scheduled times occurring at non-integral time intervals, the system comprising:

a computer;

a plurality of buckets stored in the computer, each bucket storing events to occur at a scheduled time;

wherein the buckets have no assigned order relative to one another; and

a structure organizing the scheduled times, wherein the structure is constructed and arranged to allow easy location of an earliest scheduled time;

wherein the scheduled times are represented as real numbers.

17. A system according to claim 16, wherein the structure containing the scheduled times is organized as a heap.

18. A system according to claim 16, wherein the computer includes a mixed-signal simulator for generating events and assigning times to generated events.