Go to the first, previous, next, last section, table of contents.

Overview

An overview of the rapid prototyping system is presented by showing how to solve the following simple problem.

The following system of inequalities describing a convex polyhedron representing a two dimensional iteration space (`i', `j') is given as the input.

• i >= 1
• i <= N
• j >= i
• j >= N - i
• j <= 2*i + 1

First, we will find if there exists an integer solution for this system of inequalities, i.e. if there are any valid iterations within this space.

Next, we will explore two different methods to scan the iteration space. In the first method, a loop nest is created with `i' outermost and `j' innermost. In the second method we will produce a loop nest where `j' is outermost and `i' is innermost.

Here is the LIC session that is used to perform the above mentioned tasks.

csh> lic -c
Rapid Prototyping System for Code Generation
> iter = [ 1     <= i <= N
           i     <= j
           N - i <= j
                    j <= 2*i + 1 ]
1+2*i-j >= 0
i+j-N >= 0
-i+j >= 0
-i+N >= 0
-1+i >= 0
> iter.intsol()
1
> #iter = iter.order(N i j)
> iter.code(2)

for(i = max(1, (1+N)/3); i <= N; i++)
   for(j = max(N-i, i); j <= 1+2*i; j++)

> #iter = iter.order(N j i)
> iter.code(2)

for(j = (1+N)/2; j <= 1+2*N; j++)
   for(i = max(1, N-j, j/2); i <= min(j, N); i++)

> quit
done(0)
csh>

1. LIC is invoked for Prototyping system mode
2. The system of inequalities was entered into the system. The system was assigned to the inequality variable `iter'. LIC will print the contents of the variable `iter' after it is created.
3. Applying the function `intsol()' to `iter' will determine if there exists an integer solution for the system. LIC prints 1 indicating that there is an integer solution to the system.
4. Order the inequalities in `iter' such that the variables within the inequalities are arranged with `N' outermost and `j' innermost and assign it back to `iter'. Note that `#' at the beginning of the line stops LIC from printing the results of the expression evaluated by that line.
5. Print the loop nest that will scan the system of inequalities in `iter' in the order given by the previous `order()' command. Note that `code(2)' will print only the 2nd and 3rd variables of the system, thus omitting the constant `N'.
6. The inequalities in `iter' are reordered such that `i' is innermost.
7. Print the loop nest that will scan the system of inequalities in `iter' in the order given by the previous `order()' command.
8. Exit the LIC program.

Go to the first, previous, next, last section, table of contents.