Patent
1997-04-02
2000-05-16
Voetz, Emanuel T.
G06F 945
Patent
active
060648198
ABSTRACT:
Selected code is modeled in a polyhedral dependency graph (PDG). A placement optimizer maps each element of the PDG to an optimally placed PDG. An ordering optimizer maps the placed PDG to an optimally ordered PDG. The PDG, place PDG, and ordered PDG are combined to produce a transformation script. The transformation script is applied to the selected specification description to produce optimized selected code. Optimized selected code is combined with original code to generate a control-flow optimized code. In addition, memory directives are derived from the ordered PDG model. The memory directives and optimized code are used to generate target code for simulation or software compilation.
REFERENCES:
patent: 3694813 (1972-09-01), Loh et al.
patent: 3891836 (1975-06-01), Lee
patent: 3916383 (1975-10-01), Malcom
patent: 3969698 (1976-07-01), Bollinger et al.
patent: 4177514 (1979-12-01), Rupp
patent: 4463372 (1984-07-01), Bennett et al.
patent: 4803416 (1989-02-01), Abiven et al.
patent: 5021945 (1991-06-01), Morrison et al.
patent: 5175856 (1992-12-01), Van Dyke et al.
patent: 5179702 (1993-01-01), Spix et al.
patent: 5195172 (1993-03-01), Elad et al.
patent: 5216593 (1993-06-01), Dietrich et al.
patent: 5287511 (1994-02-01), Robinson et al.
patent: 5321773 (1991-12-01), Kopec et al.
patent: 5323010 (1994-06-01), Gratton et al.
patent: 5379231 (1995-01-01), Pillage et al.
patent: 5398303 (1995-03-01), Tanaka
patent: 5459739 (1995-10-01), Handley et al.
patent: 5471408 (1995-11-01), Takamoto et al.
Franssen et al., "Modeling Multidimensional Data and Control Flow," IEEE Trans. on VLSI Systems, vol. 1, Iss. 3, pp. 319-327, Sep. 1993.
Van Swaaij et al., "Automating High Level Control Flow Transformations for DSP Memory Management," IEEE, NY, Proc. of IEEE Workshop on VLSI Sig. Proc., pp. 397-406, Oct. 28, 1992.
F.Balasa, "Formal Methodology for Linear Type Data Dependence Analysis", IMEC Res. Report, 1992.
F. Balasa, F.Catthoor, H.De Man, "Exact Evaluation of Memory Size for Multi-dimensional Signal Processing Systems", accepted for IEEE Int'l Conf. Computer-Aided Design, Santa Clara CA, Nov. 1993.
U.Banerjee, R.Eigenmann, A.Nicolau, D.Padua, "Automatic Program Parallelization", Proc. of the IEEE, invited paper, vol.81, No.2, Feb. 1993.
A.Benaini, P.Quinton, Y.Robert, Y.Saouter, B.Tourancheau, "Synthesis of a New Systolic Architecture for the Algebraic Path Problem", Science of Computer Programming, vol.15, pp.135-158, 1990.
J.Buck, S.Ha, E.Lee, D.Messerschmitt, "Ptolemy: A Framework for Simulating and Prototyping Heterogeneous Systems", Proc. European Simulation Conf., invited paper, Copenhagen, Denmark, Aug. 1992.
F.Catthoor, H.De Man, "Application-Specific Architectural Methodologies for Hign-Throughput Digital Signal and Image Processing", IEEE Trans, on Acoustics, Speech and Signal Processing, vol.38, No.2, pp. 339-349, Feb. 1990.
A.Darte, T.Rissett, R.Robert, "Loop Nest Scheduling and Transformations", Environments and Tools for Parallel Scientific Computing, J.J. Dongara, et al., editors, North Holland, 1993.
H.De Man, F.Catthoor, G.Goossens, J.Vanhoof, J.Van Meerbergen, S.Note, J.Huisken, "Architecture-Driven Synthesis Techniques for VLSI Implementation of DSP Algorithms", epecial issue on Computer-aided Design of Proc of the IEEE, vol. 78, No. 2, pp.319-335, Feb. 1990.
P.Feautrier, "Dataflow Analysis of Array and Scalar References", Int'l J. of Parallel Programming, vol.20, No.1, pp. 23-53, Feb. 1991.
F.Franssen, M.van Swaaij, F.Catthoor, H.De Man, "Modeling Piece-wise Linear and Data dependent Signal Indexing for Multi-dimensional Siganl Processing", Proc. 6th Int'l Workshop on High-Level Synthesis, Laguna Beach, CA, Nov. 1992.
F. Franssen, F.Balasa, M.van Swaaij, F.Catthoor, H.De Man, "Modeling Multidimensional Data and Control Flow", accepted for IEEE Trans on VLSI Systems, Sep. 1993.
D.Genin, P.Hilfinger, J.Rabaey, C.Scheers, H.De Man, "DSP Specification Using Silalge Language" Proc. Int'l Conf. on Acoustics, Speech and Signal Processing, Albuquerque, NM. pp. 1057-1060, Apr. 1990.
G.Goossens, J.Rabaey, J.Vandewalle, H.De Man, "An Efficient Microcode Compiler for Application Specific DSP Processors", IEEE Trans. on Computer-Aided Design,, vol.9, No.9, pp.925-937, Sep. 1990.
D.Grant, P.Denyer, I.Finlay, "Synthesis of Address Generators", Proc. IEEE Int'l Conf. on Computer-Aided Design, Santa Clara, CA, pp. 116-119, Nov. 1989.
J.Kunkel, "COSSAP: A Stream Driven Simulator", IEEE Int'l Workshop on Microelectronics in Communications, Interlaken, Switzerland, Mar. 1991.
F.Kurdahi, A.Parker, "Real: A Program for REgister ALlocation", Proc. 24th ACM/IEEE Design Automation Conf., Miami, FL, pp.210-215, Jun. 1987.
D.Lanneer, "Design Models and Data-Path Mapping for Signal Processing Architectures", Ph.D. Thesis, ESAT, K.U.Leuven, Belgium, Mar. 1993.
J-H.Lee, Y-C.Hsu, Y-L.Lin, "A New Integer Linear Programming Formulation for the Scheduling Problem in Data Path Synthesis", EDAC/IEEE, 1989.
P.Le Guernic, A.Benveniste, P.Bournai, T.Gautier, "Signal--A Data Flow-Oriented Language for Signal Processing", IEEE Trans. on Acoustics, Speech, and Signal Processing, vol.ASSP-34, No.2, pp.362-374, Apr. 1986.
W.Li, K.Pingali, "A Singular Loop Transformation Framework Based on Non-singular Matrices", Proc. 5th Annual Workshop on Languages and Compilers for Parallelism, New Haven, Aug. 1992.
P.Lippens, J.van Meerbergen, A.van der Werf, W.Verhaegh, B.McSweeney, J.Huisken, O.McArdle, "PHIDEO: A silicon Compiler for High Speed Algorithms", Proc. European Design Autom. Conf., Amsterdam, The Netherlands, pp.436-441, Feb. 1991.
D.Loveman, "Program Improvement by Source-to-Source Transformation", J. of the ACM, vol.24, No.1, pp.121-145, Jan. 1977.
M.McFarland, A.Parker, R.Camposano, "The High-Level Synthesis of Digital Systems", special issue on Computer-Aided Design in Proc. of the IEEE, vol.78, No.2, pp.301-318, Feb. 1990.
D.Moldovan, "Tradeoffs Between Time and Space Characteristics in the Design of Systolic Arrays", Proc. IEEE Int'l Symp. on Circuits and Systems, Kyoto, Japan, pp.1685-1688, Jun. 1985.
L.Nachtergaele, I.Bolsens, H.De Man, "A Specification and Simulation Front-End for Hardware Synthesis of Digital Signal Processing Applications", special issue on Simulatio of Highly Paralled Systems in Int'l J. of computer Simulation, 1992.
A. Nicolau, "Loop Quantization: A Generalized Loop Unwinding Technique", J. of Parrallel and Distributed Computing, vol. 5, pp. 568-586, 1988.
D. Padua, M. Wolfe, "Advanced Compiler Optimizations for Supercomputer," special issue of Communications of the ACM, vol. 29, No. 12, pp. 1184-1201, Dec. 1986.
P. Pochmuller, N. Wehn, M. Glesner, "Automatic Synthesis for Mechatronic Applications", Application-Driven Architecture Synthesis, F.Catthoor, L. Svensson (eds.), Kluwer Boston, pp. 167-190, 1999.
C. Polychronopoulos, Compiler Optimizations for Enhancing Parallelism and Their Impact on Architectur Design:, IEEE Trans. on Computers, vol. 37, No. 8, pp. 991-1004, Aug. 1988.
W. Pugh, "The Omega Test: A Fast and Practical Integer Programming Algorithm for Dependence Analysis", Proc. Supercomputing '91, Nov. 1991.
P. Quinton, V.Van Dongen, "The Mapping of Linear Recurrence Equations on Regular Arrays", J. of VLSI Signal Processing, vol. 1, Kluwer, Boston, pp. 95-113, 1989.
H. Sansom, L. Claesen, H. De Man, "SynGuide: An Environment for Doing Interative Correctness Preserving Transformations", Accepted for IEEE workshop on VLSI Signal Processing, Veldhoven, The Netherlands, Oct. 1993.
L. Stok, J.A.G. Jess, "Foreground Memory Management in Data in Path Synthesis", Int'l J. of Circuit Theory and Applications, vol. 20, pp. 235-255, 1992.
I. Verbauwhede, F. Catthoor, J. Vandewalle, H. De Man, "Background Memory Synthesis for Algebraic Algorithms on Multi-Processor DSP Chips", Proc. VLSI '89, Int'l Conf. on VLSI , Munich, Germany, pp. 209-218, Aug. 1989.
L. Van Gool, J. Wagemans, A. Oosterlinck, "Regularity Detection as a Strategy in Object Modeling and Recognition", SPIE Applications of Artificial Intelligence VII, vol. 1095, pp. 138-149, 1989.
J. Vanhoof, I. Bolsens, H. De
Catthoor Francky
De Man Hugo
Franssen Frank
Nachtergaele Lode
Samsom Hans
Corcoran, III Peter J.
IMEC
Voetz Emanuel T.
LandOfFree
Control flow and memory management optimization does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Control flow and memory management optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Control flow and memory management optimization will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-266499