Subject: hpff-task: Preliminary proposal for Supporting Out-Of-Core Arrays in HPF

From: [email-masked]
Date: Thu, 07 Sep 95 13:18:46 -0400

---------------------------------------------------------------------------
[email-masked] is a mailing list for discussion of control-parallel
features in HPF.  Instructions for adding or deleting yourself from this
list appear at the bottom of this message.
---------------------------------------------------------------------------

  Preliminary Proposal to provide support for OOC arrays in HPF

(The proposal is based on addressing some basic questions which are
listed at the end of this message)

We would like to start a discussion on this.

thanks
Alok, Chuck, Ken

The following proposal presents a way to support out-of-core array in HPF.
The main objectives are consistency with the "normal" HPF data mapping
directives, simplicity, and minimal extensions.

The following illustrates an example of declaring out-of-core arrays.
The only addition here is the directive OUT-OF-CORE. (Other directives
and information will follow later in this writeup)

!HPF$ TEMPLATE TEMP(100,100)
!HPF$ DISTRIBUTE TEMP(CYCLIC(B),CYCLIC(B))
!HPF$ ALIGN WITH TEMP :: A,B,C
!HPF$ OUT-OF-CORE: TEMP

This directive simply says that if nodes had infinite memory then
elements of the array will be in the memory of the processor as described
by the distribution directives. In other words, the directives describe
which processor's memory will an element be brought into when in-core.
This is a logical and simple extension of the HPF data mapping directives.

As usual, directives can be directly applied to arrays (rather than through
a template).

Restrictions: 
1) One cannot align an in-core array with an out-of-core array. E.g.,
   if A(10,10) is an OOC array and B(10) is an in-core array, it is
   not permitted to align B with A (or vice-versa) in any form, because
   not all the elements of A may be in-core, and therefore, it is
   difficult to enforce the meaning of align in such cases.
2) Others?

Association of File(s) with Arrays.

If the data for an out-of-core array comes from an input file then 
the file name must be specified. This is different from traditional
open and read/write of a file because the user does not explicitly access the
file.

For this we propose a directive

!HPF$ ASSOCIATE (<fn>, [,other parameters]) :: OOC array name

e.g., 

!HPF ASSOCIATE (filex) :: A

By default, the storage order in the file is the fortran storage order
and the element (1,1) corresponds to the first elment of the
file.

[,Other parameters] can be used to specify.
1) Storage order
2) starting element of the dataset within the file.

1) is needed if the storage order is anything other than the default
   column major.

   There are two possibilities. Use key words such as row major, column
major, or chucnks with parameters (such as chunk size in each dimension);

 OR use an explicit order, e.g., (2,1,3) which says that the outermost
dimension is 2 followed by 1 followed by 3. This may not allow chunking.

2) Starting element of the dataset is necessary if file contains some
   meta data in the beginning (e.g., a description of storage order from
   which the info in 1 will be derived) of a file, record size etc.

   This would require an open of a file, read of meta data and close
   of a file before the corresponding ASSOCIATE may be executed.

Note that it is not allowed to have a file open for regular access
 as well as for out-of-core computation because OOC computation
 provides implicit access ot a file and any explicit access
presents consistency problems.

However, the following is allowed.

	OPEN the file
	READ/WRITE/INQUIRE to your heart's content
	CLOSE the file
	(somewhere down the call chain) declare the OOC array
	use the array
	RETURN (i.e. exit the scope where the array is declared)
	now you can access the file again
The CLOSE acts as a sync point.  Similarly, the array being
deallocated acts as a sync point.

Note that this is necessary if metadats is contained within the file.

If an OCC array is used purely for scratch purposes, then it is not
necessary to associate a file with it. Compiler can choose
a name and create files in whatever way necessary. HOWEVER,
any array with which no file name is associated, must not be
read before anything is written into it (for obvious reasons).
In fact, it should be a runtime error if there is a part of the
OOC array which has not been assigned any values is read.

ASSOCIATE directive is also an executable (like redistribute) because
a user may want to process several files using the same array
(at different points in time, e.g., pipelined computations).
At any point, however, only one association exists. 

E.G., 

!HPF$ TEMPLATE TEMP(100,100)
!HPF$ DISTRIBUTE TEMP(CYCLIC(B),CYCLIC(B))
!HPF$ ALIGN WITH TEMP :: A,B,C
!HPF$ OUT-OF-CORE: TEMP

 DO i=1,numer_of_frames

    ASSOCIATE (frame.i) :: A ! Syntax to be decided of course!
    EXTRACT_NICE_FEATURES(A)
 END Do

Note one can associate multiple OOC arrays with the same file but
the consistency (if multiple assignments are done) is user's
responsiblity.

			TILING

Even when OOC distribution is provided, it may require significant
compiler analysis to figure out in what order to bring data in
to be processed. User, based on her knowledge of computation
(philosophy of HPF) can provide this hint.

For this purpose, a directive IO_DISTRIBUTE can be used, which essentially
provides a hint as to how data should be fetched into the memory.

For example, say each processors "owns" chunk of OOC data after
a (block,block) distribution. How data is to be fetched from whichin this
chunk (bunch of rows, bunch of columns, two-dim blocks) can be
described by IO_DISTRIBUTE.

Note that IO_DISTRIBUTE will also help in reorganizing data into local
files of each processor wrt to storage order within each file, if the
implementation chooses to do such a reorganization.

However, note that block size here would depend on the amount of memory
(tile size) available (and not on the NOP). The syntax for this
size specification within IO_DISTRIBUTE needs to be resolved.

One way is to do it explicitly; e.g., IO_DISTRIBUTE A(5,10), meaning
blocks of 5X10 elements...

But I believe this is a detail.
----------------------------------------------------------------

The above discussion is based on the following questions. Some of them
are not answered (in terms of a concrete proposal)

 1. Type of array: is the given array in-core or out-of-core? What is
the distribution of the array?
 2. If out-of-core, is there a corresponding file?
 3. If there exists a file, is the file persistent (input/output) or
temporary?
 4. Information about array mapping
    1. Multiple arrays mapped to the same file
    2. Multiple files mapped to the same array
 5. Information about File Mapping
    1. File Ordering
    2. File Distribution Information
 6. Hints about tiling
    1. Available Memory
    2. Tiling Parameters

* Execution Model
 Compiler has to decide underlying execution model. Two possible
models are
  1. Local Placement Model (OOC data in local space)
  2. Global Placement Model (OOC data in Shared Space)

==============================================================================
Alok Choudhary                 Phone: 315-443-4280 (Off.)
Associate Professor                   315-423-8065(home)
ECE, CIS and                    (Fax): 315-443-2583
121 Link Hall                   [email-masked] (preferred)
Syracuse University             [email-masked]
Syracuse, NY 13244.             http://www.cat.syr.edu/~choudhar

=============================================================================

---------------------------------------------------------------------------
To (un)subscribe to this list, send mail to [email-masked].
Leave the subject line blank, and in the body put the line
(un)subscribe <email-address>
---------------------------------------------------------------------------