The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
May. 02, 2000
Filed:
Jun. 24, 1997
Nimrod Megiddo, Palo Alto, CA (US);
Vivek Sarkar, Newton, MA (US);
International Business Machines Corporation, Armonk, NY (US);
Abstract
An integer programming formulation for weighted loop fusion is presented. Loop fusion is a well-known program transformation that has shown to be effective in reducing loop overhead and improving register and cache locality. Weighted loop fusion is the problem of finding a legal partition of loop nests into fusible clusters so as to minimize the total inter-cluster edge weights. Past work has shown that the weighted loop fusion problem is NP-hard. Despite the NP-hardness property, the present invention provides optimal solutions that may be found efficiently, in the context of an optimizing compiler, for weighted loop fusion problem sizes that occur in practice. An integer programming formulation for weighted loop fusion with a problem size (number of variables and constraints) that is linearly proportional to the size of the input weighted loop fusion problem is also presented. The integer programming formulation may be solved efficiently using a general integer programming package. Alternatively, a custom branch-and-bound procedure for the integer programming formulation is presented that is more efficient than the procedures used in general integer programming.