Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2006-08-29
2006-08-29
An, Meng-Al T. (Department: 2195)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S100000, C718S102000, C717S136000, C717S156000
Reexamination Certificate
active
07100164
ABSTRACT:
The present invention accepts an acyclic concurrent control-flow graph (CCFG) and produces a sequential control flow graph (SCFG) that, when executed, behaves functionally like the CCFG would if it were run on concurrent hardware. An SCFG can be easily translated into a traditional sequential programming language such as C or assembly to be executed on a traditional sequential processor.Determining the order in which CCFG nodes will be run is the first step in the process. Control edges in the CCFG constrain the order in which CCFG nodes must run; communication between threads generally impose further constraints. An easy way to further constrain a valid order of CCFG nodes is to augment the CCFG with data dependence edges (representing inter-thread communication) and to then topologically sort the nodes in the augmented graph to produce an ordering.Once the CCFG nodes are ordered, the procedure for producing the SCFG from the scheduled acyclic CCFG simulates the execution of the CCFG under an operating system supporting concurrent threads and creates an SCFG that, when executed, will reproduce the functional behavior of the CCFG running under this simulated operating system. The effects of context switching are largely compiled away by this simulation process. Each context switch is done by a single assignment that stores the state of the thread being suspended and a single branch that restores the state of the thread being resumed.
REFERENCES:
patent: 5659754 (1997-08-01), Grove et al.
patent: 6081665 (2000-06-01), Nilsen et al.
patent: 6102968 (2000-08-01), Colby et al.
patent: 6421815 (2002-07-01), Seawright
patent: 6463582 (2002-10-01), Lethin et al.
Baker, Brenda S. “An Algorithm for Structuring Flographs”, Jan 1977. Journal of the Association for Computing Machinery, vol. 24, No. 1.
Lin, Bill. “Efficient Compilation of Process-Based Concurrent Programs without Run-Time Scheduling”, Feb. 23-26, 1998.Proceedings of Design, Automation and Test in Europe, pp. 211-217.□□.
Stephen A. Edwards, “Compiling Esterel into Sequential Code,” Proceedings of the 7th International Workshop on Hardware/Software Codesign, pp. 147-151 (May 1999).
Gerard Berry, “Esterel on hardware,” Philosophical Transactions of the Royal Society of London, Series A, 339:87-104 (1992).
Gerard Berry and Georges Gonthier. “The Esterel Synchronous Programming Language: Design, Semantics, Implementation.” Science of Computer Programming, 51 pages, Nov. 1992.
Bill Lin. “Software Synthesis of Process-Based Concurrent Programs.” Proceedings of the 35thDesign Automation Conference, pp. 502-505, San Francisco, CA, Jun. 1998.
Xiaohan Zhu and Bill Lin, “Compositional Software Synthesis of Communicating Processes,” IEEE International Conference on Computer Design, Oct. 1999, pp. 646-651.
Ali Syed J
An Meng-Al T.
Kaplan Jonathan T.
Synopsys Inc.
LandOfFree
Method and apparatus for converting a concurrent control... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for converting a concurrent control..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for converting a concurrent control... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3624051