Apparatus and method for high-speed memory access

Details Apparatus and method for high-speed memory access Apparatus and method for high-speed memory access

1998-06-04

2001-08-21

Chaki, Kakali (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000

Reexamination Certificate

active

06279152

ABSTRACT:

TECHNICAL FIELD
The present invention relates to an apparatus and method for realizing high-speed memory access.
BACKGROUND ART
Conventionally, the accessibility to memory is an important factor of the performance of a program when computation for science and/or technology is performed by a vector computer.
A vector computer gains access to memory in the following methods.
(1) Consecutive access: For example, the following source program (Fortran source) is executed.
do i=1, 10
a(i)=b (i)
enddo
In this case, an array a and an array b are consecutively accessed by DO index i.
(2) Access with distance: For example, the following source program (Fortran source) is executed.
do i=1, 10, 2
a(i)=b(i)
enddo
In this case, an array a and an array b are accessed with a distance of two using a DO index i.
(3) List access: For example the following source program (Fortran source) is executed.
do i=1, 10
a(list (i))=b(list (i))
enddo
In this case, an array a and an array b are accessed at random using a value of a list array ‘list’.
The above described access methods can be arranged in the order of (1), (2), and (3) from the highest efficiency (speed). That is, the consecutive access is the highest method, and the list access is the slowest method. One of the most important objects in tuning a source program is to change a given source program into an algorithm for high-speed memory access.
However, the slowest list access method (3) cannot avoid appearance in a program algorithm, and cannot be changed into access such as the access (1) and (2).
With memory in which an address is assigned in an interleave system, there often arises a phenomenon of a bank conflict in which a plurality of access requests are transmitted to a memory bank within a predetermined time. When a bank conflict arises in list access, the access speed largely depends on a list pattern. When access concentrates on a single bank and competition occurs, the access time may be several ten times a normal value.
DISCLOSURE OF THE INVENTION
The present invention aims at realizing high-speed list access without user's tuning a source program and a bank conflict in a memory.
According to the present invention, an optimization directive line is described in the source program to optimize an access method of list access during the compilation. By describing the optimization directive line, a bank conflict can be avoided by copying data to be accessed to a work array, changing an access order at random, scalar loading, etc.
FIG. 1
shows the configuration of a processing unit according to the present invention. In
FIG. 1
, a source program
1
is a source program to be processed for higher-speed memory access.
A processing unit
2
includes a program input unit
3
, a source analysis unit
4
, a vector process unit
6
, a code generation unit
9
, etc., and performs various processes according to a program.
The program input unit
3
provides an input source program
1
for the source analysis unit
4
.
The source analysis unit
4
includes an optimization control line analysis unit
5
for analyzing an optimization control line (optimization directive line), etc., and analyzes the source program
1
.
The vector process unit
6
includes a vectorization unit
7
for vectorizing instructions, a changing unit
8
for changing list vector access, etc. and performs a vectorizing process.
The code generation unit
9
generates a code to convert a program into an executable object program
10
.
Described below are the operations of the optimization control line analysis unit
5
and the changing unit
8
.
When the optimization control line analysis unit
5
detects that an optimization directive line for changing a method of list access is inserted in the source program
1
, the changing unit
8
changes subsequent list accesses to an access method specified in the optimization directive line. The changing method can be one of the following three methods.
When the optimization control line analysis unit
5
detects an optimization directive line in the source program
1
, the changing unit
8
generates and inserts an instruction to copy a target array to be list-accessed to a work array, generates and inserts an instruction to determine the access position of the work array based on the list value of the list access, and changes the list access to the target array into access using the work array.
When the optimization control line analysis unit
5
detects an optimization directive line in the source program
1
, the changing unit
8
generates and inserts an instruction to generate a random access position, and changes all access dependent on the repetition of a loop during the list access into the generated access position.
When the optimization control line analysis unit
5
detects an optimization directive line in the source program
1
, the changing unit
8
generates and inserts a scalar instruction to load the leading position of a target array, generates and inserts an instruction to transfer the loaded scalar data to vector data of list access, and generates and inserts an instruction string using the transferred vector data.
Furthermore, a storage medium for storing a program which performs the above described processes can be generated, and the program can be loaded from the storage medium to the processing unit
2
to be executed.
Thus, list access can be converted into an appropriate access method by performing a compiling process based on the description of an optimization directive line. Therefore, high-speed list access can be realized without user's tuning a source program and a bank conflict.


REFERENCES:
patent: 5010522 (1991-04-01), Ashmore, Jr.
patent: 5274820 (1993-12-01), Gillet
patent: 5305281 (1994-04-01), Lubeck
patent: 5404531 (1995-04-01), Wakatani
patent: 5485597 (1996-01-01), Yamamoto
patent: 5721928 (1998-02-01), Umehara et al.
patent: 5799183 (1998-08-01), Iwashita
patent: 5805863 (1998-09-01), Chang
patent: 5835436 (1998-11-01), Ooishi
patent: 5842035 (1998-11-01), Nishikawa
patent: 4-262458 (1992-09-01), None
patent: 6-274351 (1994-09-01), None
patent: 8-171554 (1996-07-01), None
Nam-Henschen teach Compiling Recursive Prolog Programs with List Structure into Procedural Languages, Computer Software and Applications Conference, 1991. COMPSAC' 91, Proceedings of the Fifteenth Annual International, IEEE, Sep. 1991.*
Rodgers-Page, An efficient list representation and access scheme for artificial intelligence applications, IEEE 1998, Apr. 1998.

Affiliated with

Also associated with

Rating

Apparatus and method for high-speed memory access does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Apparatus and method for high-speed memory access, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for high-speed memory access will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2505921