Browse Prior Art Database

Algorithm for Uniform Segmentation of a Reference-Type Nested Loop

IP.com Disclosure Number: IPCOM000034227D
Original Publication Date: 1989-Jan-01
Included in the Prior Art Database: 2005-Jan-27
Document File: 3 page(s) / 68K

Publishing Venue

IBM

Related People

Honjou, N: AUTHOR

Abstract

This article describes an algorithm for uniform segmentation of a reference-type nested loop (RNL), whose structure is shown in Fig. 1. The algorithm uses a formula to calculate how many loop iterations are necessary for the segmentation. FIG. 1. A Reference-Type Nested Loop Written in FORTRAN. DO 1 J1=1,N ,1 DO 2 J2=1,J1 ,1 DO 3 J3=1,J2 ,1 . . DO M JM=1,J(M-1) ,1 M CONTINUE . .

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 57% of the total text.

Page 1 of 3

Algorithm for Uniform Segmentation of a Reference-Type Nested Loop

This article describes an algorithm for uniform segmentation of a reference-type nested loop (RNL), whose structure is shown in Fig.
1. The algorithm uses a formula to calculate how many loop iterations are necessary for the segmentation. FIG. 1. A Reference-Type Nested Loop Written in FORTRAN. DO 1 J1=1,N ,1

DO 2 J2=1,J1 ,1

DO 3 J3=1,J2 ,1

.

.

DO M JM=1,J(M-1) ,1

M CONTINUE

.

.

3 CONTINUE

2 CONTINUE

1 CONTINUE This RNL is characterized by (1) the nesting of loops (M-fold), and (2) the expressions which have constant initial values of 1, constant increments of 1, and test values each of which refers to the DO variable value of the loop immediately outside. The test value of the outermost loop is constant positive integer N. We intend to divide the original RNL uniformly into n segments, keeping the increments at the original value of 1. Here, 'uniform' means that the numbers of iterations of the segments match with each other to within a difference of one iteration. To carry out the uniform segmentation, we need to know the numbers of iterations of both the original RNL and partial RNLs, which are parts of the original RNL. The most primitive way to obtain the numbers is by simple enumeration. In the present algorithm, a formula is used to calculate the number of iterations in an RNL. The total number of iterations of the RNL is given by (M+N-1)!/M!(N-1)!, and the number of iterations of the general m-fold RNL having the test value of the outermost loop (k), which is a partial RNL, is given by the function L(m,k)=(m+k-1)!/m!(k-1)!. The present algorithm takes full advantage of this formula. Thus, the complexity of the present algorithm becomes (O(N*M*n)), which is 1/N**(M-1) that of the algorithm (O(N**M)) using

(Image Omitted)

the simple enumeration method. Here the * sign denotes multiplication and the ** sign exponentiation. The larger the N and/or M values are, the more efficient the segmentation by the present algorithm in comparison with the algorithm employing the simple enumeration method. Segmentation is equivalent to determining the expressions of the partial RNLs, i.e., the initial values {Iti} and the final values {Nti} for the i-th nested lo...