Boots – shoes – and leggings
Patent
1997-07-25
1999-09-14
Hafiz, Tariq R.
Boots, shoes, and leggings
395705, 395707, 364148, G06F 945
Patent
active
059535318
ABSTRACT:
An optimized set of block sizes for a nest of loops for improved data locality is determined by estimating a memory cost per iteration as a function of the block sizes and selecting a set of block sizes that yield a minimum memory cost per iteration subject to a plurality of constraints. An objective function is an estimated memory cost per iteration as a function of the block sizes. An optimal solution is provided by evaluating the objective function for candidate points in the iteration space. These candidate points comprise: corner points of the iteration space, intersections between constraints and the edges of the iteration space, zero-derivative points for the curve that is the intersection of constraints with the objective function, intersection points between constraints, and local optimum of the objective function. Alternatively, an optimized set of block sizes for a nest of loops may be determined by iteratively searching the iteration space for the optimal solution. The advantages provided include improved compiler optimization, improved selection of loop tile sizes, improved execution time for selection of loop block sizes, improved data access locality, improved execution time of nested program loops, different optimal block sizes for each loop of a loop nest, optimal block sizes for a loop nest containing an array variable whose number of dimensions are different from the number of loops in the loop nest, and optimal block sizes for a loop nest containing non-uniformly generated data.
REFERENCES:
patent: 4656582 (1987-04-01), Chaitin et al.
patent: 5193180 (1993-03-01), Hastings
patent: 5471593 (1995-11-01), Branigin
patent: 5535393 (1996-07-01), Reeve et al.
patent: 5659753 (1997-08-01), Murphy et al.
patent: 5713010 (1998-01-01), Buzbee et al.
Waters, "Automatic transformation of series expressions into loops", ACM Trans. Lang. & Syst. vol. 13, No. 1, pp. 52-96, Jan. 1991.
Carr et al., "Compiler optimizations for improving data loacality", ASPLOS-ACM, pp. 252-262, Oct. 1994.
Carr et al., "Improving the ratio of memory operations to floating point operations in loops", ACM Trans. Prog. Lang. & Syst., vol. 16, No. 6, pp. 1768-1810, Nov. 1994.
Wei Li, Compiler cache optimizations for banded matrix problems, ICS 95, ACM, pp. 21-30, 1995.
Li et al., Exploiting cache affnity in software cache coherence, ICS 94, ACM, Jul. 1997, pp. 264-273, 1994.
Bhattacharya et al., Performance analysis and optimization of schedules for conditional and loop intensive specifications, DAC 94, Procedings of 31 st Annual Conf., Design Automation, pp. 491-496, 1994.
Ohta et al., Optimal tile size adjustment in compiling general DOACROSS loop nests., ICS 95, ACM Jun. 1995, pp. 270-279.
Debray, Saumya, Abstract interpretation and low level code optimization, PEPM 95, ACM, pp. 111-121, 1995.
Wang Ko, Precise compile time performance prediction for superscalar based computers, SIGPLAN 94, ACM Jun. 1994, pp. 73-84.
Megiddo Nimrod
Sarkar Vivek
Hafiz Tariq R.
International Business Machines - Corporation
Johnson Prentiss W.
Khatri Anil
LandOfFree
Method of, system for, and computer program product for minimizi 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 of, system for, and computer program product for minimizi, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of, system for, and computer program product for minimizi will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1518989