Data processing: software development – installation – and managem – Software program development tool – Code generation
Reexamination Certificate
2009-01-31
2011-11-15
Rutten, James D (Department: 2197)
Data processing: software development, installation, and managem
Software program development tool
Code generation
C717S114000, C717S136000
Reexamination Certificate
active
08060857
ABSTRACT:
A method and a system for transformation-based program generation using two separate specifications as input: An implementation neutral specification of the desired computation and a specification of the execution platform. The generated implementation incorporates execution platform opportunities such as parallelism. Operationally, the invention has two broad stages. First, it designs the abstract implementation in the problem domain in terms of an Intermediate Language (IL) that is unfettered by programming language restrictions and requirements. Concurrently, the design is evolved by specializing the IL to encapsulate a plurality of desired design features in the implementation such as partitioning for multicore and/or instruction level parallelism. Concurrently, constraints that stand in for implied implementation structures are added to the design and coordinated with other constraints. Second, the IL is refined into implementation code. With this invention, porting an implementation neutral computation to an arbitrary architecture can be automated.
REFERENCES:
patent: 4710872 (1987-12-01), Scarborough
patent: 5237691 (1993-08-01), Robinson et al.
patent: 5499371 (1996-03-01), Heminger et al.
patent: 5535393 (1996-07-01), Reeve et al.
patent: 5790863 (1998-08-01), Simonyi
patent: 5815713 (1998-09-01), Sanders
patent: 5822593 (1998-10-01), Lamping et al.
patent: 5896537 (1999-04-01), Landi et al.
patent: 5911072 (1999-06-01), Simonyi
patent: 6088511 (2000-07-01), Hardwick
patent: 6212672 (2001-04-01), Keller et al.
patent: 6314555 (2001-11-01), Ndumu et al.
patent: 6314562 (2001-11-01), Biggerstaff
patent: 6370681 (2002-04-01), Dellarocas et al.
patent: 6408431 (2002-06-01), Heughebaert et al.
patent: 6460176 (2002-10-01), Suehiro et al.
patent: 6502234 (2002-12-01), Gauthier et al.
patent: 6574791 (2003-06-01), Gauthier et al.
patent: 6708331 (2004-03-01), Schwartz
patent: 6745384 (2004-06-01), Biggerstaff
patent: 6889373 (2005-05-01), Fukase et al.
patent: 6966054 (2005-11-01), Simonyi
patent: 7017146 (2006-03-01), Dellarocas
patent: 7140000 (2006-11-01), Yucel
patent: 7146347 (2006-12-01), Vazquez et al.
patent: 7152228 (2006-12-01), Goodwin et al.
patent: 7181734 (2007-02-01), Swamy et al.
patent: 7219328 (2007-05-01), Schloegel et al.
patent: 7313773 (2007-12-01), Braun et al.
patent: 7334216 (2008-02-01), Molina-Moreno
patent: 7743362 (2010-06-01), Peck et al.
patent: 7900189 (2011-03-01), O'Brien
patent: 2005/0144226 (2005-06-01), Purewal
References list included in external document submitted as a file named References.pdf.
Saman Amarasinghe: The Looming Software Crisis due to the Multicore Menace, presentation, Computer Science and Artificial Intelligence Laboratory, MIT, also at http://groups.csail.mit.edu/commit/papers/06/MulticoreMenace.pdf (2006) 1-55.
APL (programming language), Wikipedia, the free encyclopedia, (Apr. 4, 2011) 1-19.
Loop Optimization, Wikipedia, (May 23, 2011), pp. 1.
John Backus: Can Programming be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs, Communications of the ACM, Aug. 1978, vol. 21, No. 8, 613-641.
Roman Barták: Constraint Programming: In Pursuit of the Holy Grail, in Proceedings of the Week of Doctoral Students (WDS99), Part IV, MatFyzPress, Prague (Jun. 1999) 555-564.
Don Batory and Sean O'Malley: The Design and Implementation of Hierarchical Software Systems with Reusable Components, ACM Transactions on Software Engineering, vol. 1, No. 4, (Oct. 1992) 355-398.
Don Batory, Vivek Singhal, Marty Sirkin, and Jeff Thomas: Scalable Software Libraries. Symposium on the Foundations of Software Engineering. Los Angeles, California (1993) 191-199.
Ted J. Biggerstaff: A Perspective of Generative Reuse, Annals of Software Engineering, Baltzer Science Publishers, AE Bussum, The Netherlands (1998b) pp. 44.
Ted J. Biggerstaff: Pattern Matching for Program Generation: A User Manual. Microsoft Research Technical Report MSR-TR-98-55 (1998d) pp. 47.
Ted J. Biggerstaff: Fixing Some Transformation Problems. Automated Software Engineering Conference, Cocoa Beach, Florida (1999) pp. 10.
Ted J. Biggerstaff: A New Architecture of Transformation-Based Generators, IEEE Transactions on Software Engineering, vol. 30, No. 12 (Dec. 2004) 1036-1054.
Guy E.Blelloch, Jonathan C.Hardwick, Siddhartha Chatterjee, Jay Sipelstein, and Marco Zagha: Implementation of a Portable Nested Data-Parallel Language, in Proceedings of PPOPP '93 Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, (1993) 102-111.
Guy Blelloch: Programming Parallel Algorithms, Communications of the ACM, 39 (3) (Mar. 1996) 85-97.
Guy E.Blelloch, and Bruce M. Maggs: Parallel Algorithms, in Algorithms and theory of computation handbook, Chapman & Hall/CRC, (Jan. 2010) pp. 44.
Lucas Bordeaux, Youssef Hamadi, and Lintao Zhang: Propositional Satisfiability and Constraint Programming: A comparative survey, ACM Computing Surveys, vol. 38, No. 4, (Dec. 2006) pp. 54.
A.Borning: The Programming Language Aspects of ThingLab, A Constraint-Oriented Simulation Laboratory, in ACM Transactions on Programming Languages and Systems, 3(4), (1981) 353-387.
Bradford L. Chamberlain: Choi, Sung-Eun, Deitz, Steven J. and Snyder, Lawrence: The High-Level Parallel Language ZPL Improves Productivity and Performance, Proceedings of the IEEE International Workshop on Productivity and Performance in High-End Computing, (2004) 1-10.
Don Clark: Racing to Gain Edge on Multicore Chips, Wall Street Journal, Mar. 17, 2008 pp. 1.
Daniel E.Cooke, J. Nelson Rushton, Brad Nemanich, Robert G.Watson, and Per Andersen: Normalize, Transpose, and Distribute: An Automatic Approach to Handling Nonscalars, ACM Transactions on Programming Languages and Systems, vol. 30, No. 2, (2008), pp. 49.
Tzilla Elrad, Robert E. Filman and Atef Bader: Aspect-Oriented Programming, Communications of the ACM, vol. 44, No. 10 (2001) 29-32.
Jung Kim Foo and David Garlan: Analyzing Architectural Styles, Journal of Systems and Software (2010) 1-54.
Fortran—Wikipedia, the free encyclopedia, (Apr. 4, 2011) pp. 21.
Franz Franchetti, Yevgen Voronenko and Markus Puschel: FFT Program Generation for Shared Memory:SMP and Multicore, SC2006, (Nov. 2006) pp. 12.
L.J. Guibas and D. K. Wyatt: Compilation and Delayed Evaluation in APL, Fifth Annual ACM Symposium Principles of Programming Languages, (1978) 1-8.
Halfhill, Tom R.: Parallel Processing with CUDA, Microprocessor Report, (Jan. 2008) pp. 8.
M. W.Hall, S. P.Amarasinghe, B. R.Murphy, S. W.Liao, and M. S.Lam: Interprocedural Parallelization Analysis in SUIF ACM Transactions on Programming Languages and Systems, vol. 27, No. 4, (Jul. 2005) 662-731.
Gwan-Hwan Hwang, Jenq Kuen Lee, and Dz-Ching Ju: An Array Operation Synthesis Scheme to Optimize Fortran 90 Programs, Conference Title: Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), Jul. 1995; Published in SIGPLAN Notices, 30(8):112-22 (Aug. 1995) 112-122.
Neil D.Jones: An Introduction to Partial Evaluation, ACM Computing Surveys, vol. 28, No. 3 (1996) 480-503.
W. M. Johnson, J. R. P. Hanna, and R. J.Millar: Advances in Dataflow Programming Languages, ACM Computing Surveys, vol. 36, No. 1 (Mar. 2004) 1-34.
Elaine Kant: Synthesis of Mathematical Modeling Software, IEEE Software, (May 1993) 30-41.
M. D Katz and D.Volper: Constraint Propagation in Software Libraries of Transformation Systems, International Journal of Software Engineering and Knowledge Engineering, 2, 3 (1992) 355-374.
Gregor Kiczales and Mira Mezini: Aspect-Oriented Programming and Modular Reasoning, International Conference Software Engineering, (May 2005) 49-58.
Christian Schulte and Peter J.Stuckey: Efficient Constraint Propagation Engines, ACM Transactions on Programming Languages and Systems, vol. 31, No. 1, (2009) pp. 43.
James Larus and Christos Kozyrakis: Transactional Memory, Communications of the ACM, (Jul. 2008), pp. 80-88.
John Markoff: Race is on to Advance Software for Chips, New York Times, (Apr. 30, 2008) pp. 2.
Kiminori Matsuzaki, Hideya Iwasaki, Kento Emot
Biggerstaff Ted J.
Rutten James D
LandOfFree
Automated partitioning of a computation for parallel or... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automated partitioning of a computation for parallel or..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automated partitioning of a computation for parallel or... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4277208