JPH03257534A - Memory allocating system - Google Patents
Memory allocating systemInfo
- Publication number
- JPH03257534A JPH03257534A JP5699290A JP5699290A JPH03257534A JP H03257534 A JPH03257534 A JP H03257534A JP 5699290 A JP5699290 A JP 5699290A JP 5699290 A JP5699290 A JP 5699290A JP H03257534 A JPH03257534 A JP H03257534A
- Authority
- JP
- Japan
- Prior art keywords
- parallel processing
- intermediate text
- processing part
- program
- memory
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Devices For Executing Special Programs (AREA)
- Multi Processors (AREA)
Abstract
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明はメモリ割り当て方式に関し、特にマルチプロセ
ッサによる並列処理に対するコン１＜イラのメモリ割り
合て方式に関する。DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a memory allocation method, and particularly to a memory allocation method for parallel processing by multiprocessors.
従来、マルチプロセッサシステムに対して、高級プログ
ラミング言語で記述された原始プログラムを入力し、並
列処理を行う目的プログラムを生成するコンパイラにお
いて、マルチプロセッサにより並列処理を実行する場合
に対して、原始プログラム中の並列処理の実行が可能な
処理部分で各プロセッサが局所的に使用するデータのメ
モリ上の割り当て位置を決定するときに、プロセッサ間
でバンク競合が発生するか否かを考慮せず、自由に割り
当てている。Conventionally, compilers input a source program written in a high-level programming language to a multiprocessor system and generate a target program for parallel processing. When determining the memory allocation location of data that each processor uses locally in a processing part that can execute parallel processing, it is possible to freely Assigned.
このような従来のメモリ割り当て方式は、コンパイラに
おいて、原始プログラムを入力し、並列処理を行う目的
プログラムを生成する場合に、原始プログラム中の並列
処理の実行が可能な処理部分で各プロセッサが局所的に
使用するデータのメモリ上の割り当て位置を決定すると
きに、並列処理の実行時にプロセッサ間でバンク競合が
発生するか否かを考慮しない為に、バンク競合か発生し
ないようにメモリ上に割り当てることができる場合ても
、バンク競合が発生するようにメモリに割り当ててしま
うので、マルチブロセ・ソサによる並列処理の実行時に
、特に並列処理開始直後や同期した直後の並列処理の再
開時などに、プロセ・フサ間でバンク競合が発生し、目
的プログラムを高速に実行することができないという欠
点を有している。In this conventional memory allocation method, when a compiler inputs a source program and generates a target program that performs parallel processing, each processor locally When deciding where to allocate data in memory to be used for, we do not take into consideration whether or not bank conflicts will occur between processors when executing parallel processing, so we allocate data in memory so that bank conflicts do not occur. Even if it is possible, memory will be allocated in such a way that bank contention will occur, so when executing parallel processing using multi-processor processing, especially when parallel processing is restarted immediately after starting parallel processing or immediately after synchronization, the process This has the disadvantage that bank contention occurs between the frames, making it impossible to execute the target program at high speed.
本発明のメモリ割り当て方式は、マルチプロセッサシス
テムに対して、高級プログラミング言語で記述された原
始プログラムを入力し、並列処理を行う目的プログラム
を生成するコンパイラのメモリ割当て方式において、
高級プログラミング言語で記述された原始プログラムを
入力し、構文解析を行って第１の中間子キストを生成す
る構文解析部と、
前記構文解析部により生成された第１の中間テキストを
入力し、原始プログラム中の並列処理の実行が可能な処
理部分を検出し、検出した処理部分の中で各プロセッサ
が局所的に使用するデータを並列処理部分情報テーブル
に登録する並列処理部分情報抽出部と、
前記並列処理部分情報抽出部により作成された並列処理
部分情報テーブルから並列処理部分の中で各プロセッサ
が局所的に使用するデータを入力し、並列処理部分をマ
ルチプロセッサで並列実行する場合に各プロセッサが局
所的に使用するデータのメモリ上の割り当て位置をプロ
セッサ間でメモリのバンク競合が発生しないように決定
し、決定した割り合て位置情報をデータ割り当て情報テ
ーブルに登録するデータ割り当て部と、前記構文解析部
により生成された第１の中間テキスト中の並列処理部分
を入力し、前記データ割り当て部で作成されたデータ割
り当て情報テーブル中の割り当て位置情報に従って、第
１の中間テキストを変形して第２の中間テキストを生成
する中間テキスト変形部と、
前記中間テキスト変形部で生成された第２の中間テキス
トを入力し、目的プログラムを生成する目的プログラム
生成部とを前記コンパイラに含んでｍ戒されている。The memory allocation method of the present invention is a memory allocation method for a compiler that inputs a source program written in a high-level programming language to a multiprocessor system and generates a target program that performs parallel processing. a syntax analysis unit that inputs a source program created by the syntax analyzer and generates a first intermediate text by parsing the syntax; and a syntax analysis unit that inputs the first intermediate text generated by the syntax analysis unit and executes parallel processing in the source program. a parallel processing partial information extraction unit that detects a processing part that is possible and registers data locally used by each processor in a parallel processing partial information table in the detected processing part; and the parallel processing partial information extraction unit Input the data used locally by each processor in the parallel processing part from the created parallel processing part information table, and calculate the data used locally by each processor when executing the parallel processing part in parallel on multiple processors. a data allocation unit that determines allocation positions on memory so that memory bank conflicts do not occur between processors, and registers the determined ratio position information in a data allocation information table; an intermediate that inputs parallel processing portions in the first intermediate text and generates a second intermediate text by transforming the first intermediate text according to allocation position information in the data allocation information table created by the data allocation unit; The compiler is required to include a text transformation section, and an object program generation section that receives the second intermediate text generated by the intermediate text transformation section and generates an object program.
次に、本発明の一実施例について図面を参照して説明す
る。Next, an embodiment of the present invention will be described with reference to the drawings.
第１図は本発明のメモリ割り当て方式の一実施例を示す
機能ブロック図である。FIG. 1 is a functional block diagram showing an embodiment of the memory allocation method of the present invention.
第１図に示すように、コンパイラ２の構文解析部２１は
、原始プログラム１を入力して構文解析を行い、第１の
中間テキスト３を生成する。As shown in FIG. 1, the syntax analysis unit 21 of the compiler 2 inputs the source program 1, performs syntax analysis, and generates the first intermediate text 3.
次に、並列処理部分情報抽出部２２は、第１の中間テキ
スト３を入力し、原始プログラム１中の並列処理の実行
が可能な処理部分を検出し、検出した処理部分の中で各
プロセッサが局所的に使用するデータを並列処理部分情
報テーブル４に登録する。Next, the parallel processing part information extraction unit 22 inputs the first intermediate text 3, detects a processing part in the source program 1 that can execute parallel processing, and in the detected processing part, each processor Data to be used locally is registered in the parallel processing partial information table 4.
次に、データ割り当て部２３は、並列処理部分情報テー
ブル４から並列処理部分の中で各プロセッサが局所的に
使用するデータを入力し、並列処理部分をマルチプロセ
ッサで並列実行する場合番こ各プロセッサが局所的に使
用するデータのメモリ上の割り当て位置をプロセッサ間
でメモリのノくンク競合が発生しないように決定し、決
定した割り当て位置情報をデータ割り当て情報テーブル
５に登録する。Next, the data allocation unit 23 inputs data to be locally used by each processor in the parallel processing part from the parallel processing part information table 4, and when the parallel processing part is executed in parallel by multiple processors, The memory allocation position of data to be used locally is determined in such a way that no memory knock conflict occurs between processors, and the determined allocation position information is registered in the data allocation information table 5.
次に、中間テキスト変形部２４は、第１の中間テキスト
３中の並列処理部分を入力し、データ割り当て情報テー
ブル５中の割り当て位置情報に従って、第１の中間テキ
スト３を変形して第２の中間テキスト６を生成する。Next, the intermediate text transformation unit 24 inputs the parallel processing portion in the first intermediate text 3, transforms the first intermediate text 3 according to the allocation position information in the data allocation information table 5, and converts the first intermediate text 3 into a second intermediate text. Generate intermediate text 6.
次に、目的プログラム生成部２５は、中間テキスト変形
部２４で生成した第２の中間テキスト６を入力して、目
的プログラム７を生成する。Next, the target program generation unit 25 receives the second intermediate text 6 generated by the intermediate text transformation unit 24 and generates the target program 7.
第２図は本発明を適用した場合に効果のあるＦＯＲＴＲ
ＡＮ原始プログラムの例を示す図である。Figure 2 shows the FORTR that is effective when the present invention is applied.
FIG. 3 is a diagram showing an example of an AN source program.
第２図＜７）ＦＯＲＴＲＡＮ原始プログラム１００を従
来のコンパイラにより翻訳すると、この原始プログラム
中の並列処理の実行が可能な処理部分で各プロセッサが
局所的に使用する配列Ａのメモリ上の割り当て位置を決
定するときに、並列処理の実行時にプロセッサ間でバン
ク競合が発生するか否かを考慮しない為に、配列Ａのメ
モリ上の割り当て位置をバンク競合が発生するように割
り当てている。Figure 2 <7) When the FORTRAN source program 100 is translated by a conventional compiler, the memory allocation location of the array A used locally by each processor in the processing part of the source program that can execute parallel processing is calculated. At the time of determination, in order to avoid considering whether or not bank conflict will occur between processors during execution of parallel processing, the memory allocation position of array A is allocated in such a way that bank conflict will occur.
従って、マルチプロセッサによる並列処理の実行時に、
同期をとる為の外部サブルーチン呼び出し１２０の実行
の直後に、並列処理部分１３０において、プロセッサ間
でバンク競合が発生し、目的プログラムを高速に実行す
ることができない。Therefore, when executing parallel processing using multiprocessors,
Immediately after execution of the external subroutine call 120 for synchronization, bank contention occurs between processors in the parallel processing section 130, making it impossible to execute the target program at high speed.
第３図は第２図のＦＯＲＴＲＡＮｉ始プログラム１００
中の並列処理部分１３０に対して本発明を適用したコン
パイラにより生成された目的プログラムが実行する処理
の一例を示す図である。Figure 3 shows the FORTRANi starting program 100 in Figure 2.
3 is a diagram illustrating an example of a process executed by a target program generated by a compiler to which the present invention is applied to a parallel processing portion 130 in FIG.
第２図のＦＯＲＴＲＡＮ原始プログラム１００を本発明
を適用したコンパイラで翻訳すると、第３図に示すよう
に、ステップ２１０で、並列処理部分１３０の実行時に
、実行するプロセッサの番号によりそれぞれ分岐し、ス
テップ２２０−０で、プロセッサ＃０が実行する並列処
理部分１３０中の配列Ａの先頭番地に対して０番目のバ
ンクを使用し、ステップ２２０−１で、プロセッサ＃１
が実行する並列処理部分１３０中の配列Ａの先頭番地に
対して１番目のバンクを使用し、・・・・・ステップ２
２０−Ｎで、プロセッサ＃Ｎが実行する並列処理部分１
３０中の配列Ａの先頭番地に対してＮ番目のバンクを使
用するＦＯＲＴ：ＲＡＮ目的プログラム２００を生成す
る。When the FORTRAN source program 100 shown in FIG. 2 is translated by a compiler to which the present invention is applied, as shown in FIG. In step 220-0, the 0th bank is used for the first address of array A in the parallel processing part 130 executed by processor #0, and in step 220-1, processor #1
The first bank is used for the first address of array A in the parallel processing part 130 executed by . . . Step 2
20-N, parallel processing part 1 executed by processor #N
A FORT:RAN purpose program 200 that uses the Nth bank for the first address of array A in 30 is generated.
従って、マルチプロセッサによる並列処理の実行時に、
同期をとる為の外部サブルーチン呼び出し１２０の実行
の直後に、並列処理部分１３０において、プロセッサ間
でバンク競合が発生しない為に、ＦＯＲＴＲＡＮ目的プ
ログ−ラム２００を高速に実行することができる。Therefore, when executing parallel processing using multiprocessors,
Immediately after the execution of the external subroutine call 120 for synchronization, the FORTRAN objective program 200 can be executed at high speed because bank contention does not occur between processors in the parallel processing section 130.
以上説明したように、本発明のメモリ割り当て方式は、
コンパイラで原始プログラムを入力して並列処理を行う
目的プログラムを生成する場合に、原始プログラム中の
並列処理の実行が可能な処理部分に対して、各プロセッ
サが局所的に使用するデータのメモリ上の割り当て位置
を決定するときに、並列処理の実行時にプロセッサ間で
バンク競合が発生するか否かを考慮し、バンク競合が発
生しないようにメモリ上に割り当てる為に、マルチプロ
セッサによる並列処理の実行時に、特に並列処理の開始
直後や同期した直後の並列処理の再開時などに、プロセ
ッサ間でバンク競合が発生せず、目的プログラムを高速
に実行することができるという効果を有している。As explained above, the memory allocation method of the present invention is
When a compiler inputs a source program and generates a target program that performs parallel processing, it stores the data locally used by each processor in memory for the parts of the source program that can execute parallel processing. When determining the allocation position, consider whether or not bank conflicts will occur between processors when executing parallel processing, and in order to allocate on memory to prevent bank conflicts from occurring when executing parallel processing using multiprocessors. This has the advantage that bank contention does not occur between processors, especially when parallel processing is restarted immediately after starting parallel processing or immediately after synchronization, and the target program can be executed at high speed.
第１図は本発明のメモリ割り当て方式の一実施例を示す
機能ブロック図、第２図は本発明を適用した場合に効果
のあるＦＯＲＴＲＡＮ原始プログラムの例を示す図、第
３図は第２図のＦＯＲＴＲＡＮ原飴プログラム１００中
の並列処理部分１３０に対して本発明を適用したコンパ
イラにまり生成された目的プログラムが実行する処理の
一例を示す図である。
１・・・原始プログラム、２・・・コンパイラ、３・・
・第１の中間テキスト、４・・・並列処理部分情報テー
ブル、５・・・データ割り当て情報テーブル、６・・・
第２の中間テキスト、７・・・目的プログラム、２１・
・・構文解析部、２２・・・並列処理部分情報抽出部、
２３・・・データ割り当て部、２４・・・中間テキスト
変形部、２５・・・目的プログラム生成部、１００・・
・ＦＯＲＴＲＡＮ原始プログラム、１１０・・・並列処
理で実行する外部サブルーチン、１２０・・・同期をと
る為の外部サブルーチン呼び出し、１３０・・・同期直
後の並列処理の実行再開時に配列Ａに関してバンク競合
する可能性がある並列処理部分、２００・・・ＦＯＲＴ
ＲＡＮ目的プログラム、２１０・・・並列処理の実行時
に実行するプロセッサの番号により分岐する、２２０−
０・・・配列Ａの先頭番地は０番目のバンクを使用する
、２２０−１・・・配列Ａの先頭番地は１番目のバンク
を使用する。FIG. 1 is a functional block diagram showing an embodiment of the memory allocation method of the present invention, FIG. 2 is a diagram showing an example of a FORTRAN source program that is effective when the present invention is applied, and FIG. 2 is a diagram showing an example of processing executed by a target program generated by a compiler to which the present invention is applied to the parallel processing portion 130 in the FORTRAN original candy program 100 of FIG. 1... Source program, 2... Compiler, 3...
- First intermediate text, 4... Parallel processing partial information table, 5... Data allocation information table, 6...
Second intermediate text, 7...Objective program, 21.
...Syntax analysis unit, 22...Parallel processing partial information extraction unit,
23... Data allocation unit, 24... Intermediate text transformation unit, 25... Target program generation unit, 100...
- FORTRAN source program, 110...External subroutine executed in parallel processing, 120...External subroutine call for synchronization, 130...Possible bank conflict regarding array A when resuming execution of parallel processing immediately after synchronization. parallel processing part, 200...FORT
RAN purpose program, 210... Branches depending on the number of the processor to be executed when executing parallel processing, 220-
0...The starting address of array A uses the 0th bank.220-1...The starting address of array A uses the 1st bank.
Claims (1)
グ言語で記述された原始プログラムを入力し、並列処理
を行う目的プログラムを生成するコンパイラのメモリ割
り当て方式において、高級プログラミング言語で記述さ
れた原始プログラムを入力し、構文解析を行って第１の
中間テキストを生成する構文解析部と、 前記構文解析部により生成された第１の中間テキストを
入力し、原始プログラム中の並列処理の実行が可能な処
理部分を検出し、検出した処理部分の中で各プロセッサ
が局所的に使用するデータを並列処理部分情報テーブル
に登録する並列処理部分情報抽出部と、 前記並列処理部分情報抽出部により作成された並列処理
部分情報テーブルから並列処理部分の中で各プロセッサ
が局所的に使用するデータを入力し、並列処理部分をマ
ルチプロセッサで並列実行する場合に各プロセッサが局
所的に使用するデータのメモリ上の割り当て位置をプロ
セッサ間でメモリのバンク競合が発生しないように決定
し、決定した割り合て位置情報をデータ割り当て情報テ
ーブルに登録するデータ割り当て部と、 前記構文解析部により生成された第１の中間テキスト中
の並列処理部分を入力し、前記データ割り当て部で作成
されたデータ割り当て情報テーブル中の割り当て位置情
報に従って、第１の中間テキストを変形して第２の中間
テキストを生成する中間テキスト変形部と、前記中間テ
キスト変形部で生成された第２の中間テキストを入力し
、目的プログラムを生成する目的プログラム生成部とを
前記コンパイラに含むことを特徴とするメモリ割り当て
方式。[Claims] In a memory allocation method of a compiler that inputs a source program written in a high-level programming language to a multiprocessor system and generates a target program that performs parallel processing, A syntax analysis unit that inputs a program and performs syntax analysis to generate a first intermediate text; and a syntax analysis unit that inputs the first intermediate text generated by the syntax analysis unit and can execute parallel processing in the source program. a parallel processing part information extraction unit that detects a processing part and registers data locally used by each processor in the detected processing part in a parallel processing part information table; Input the data used locally by each processor in the parallel processing part from the parallel processing part information table that was created. a data allocation unit that determines the allocation position of the memory so that memory bank contention does not occur between the processors, and registers the determined ratio position information in a data allocation information table; Intermediate text transformation that inputs a parallel processing part in the intermediate text and transforms the first intermediate text to generate a second intermediate text according to the allocation position information in the data allocation information table created by the data allocation unit. and a target program generation unit that receives the second intermediate text generated by the intermediate text transformation unit and generates a target program.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5699290A JPH03257534A (en) | 1990-03-07 | 1990-03-07 | Memory allocating system |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5699290A JPH03257534A (en) | 1990-03-07 | 1990-03-07 | Memory allocating system |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH03257534A true JPH03257534A (en) | 1991-11-18 |
Family
ID=13042990
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP5699290A Pending JPH03257534A (en) | 1990-03-07 | 1990-03-07 | Memory allocating system |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH03257534A (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2008545187A (en) * | 2005-06-30 | 2008-12-11 | アンテルユニヴェルシテール・ミクロ−エレクトロニカ・サントリュム・ヴェー・ゼッド・ドゥブルヴェ | Memory arrays for multiprocessor systems |
-
1990
- 1990-03-07 JP JP5699290A patent/JPH03257534A/en active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2008545187A (en) * | 2005-06-30 | 2008-12-11 | アンテルユニヴェルシテール・ミクロ−エレクトロニカ・サントリュム・ヴェー・ゼッド・ドゥブルヴェ | Memory arrays for multiprocessor systems |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0830561A (en) | Method and compiler for parallel execution of program | |
| JP2009151645A (en) | Parallel processing device and program parallelization device | |
| US20170168790A1 (en) | Parallelization method, parallelization tool, and in-vehicle apparatus | |
| JPH03126133A (en) | Compiler processing method | |
| JPH03257534A (en) | Memory allocating system | |
| JPH09293057A (en) | Task allocation method in hierarchical structure type multiprocessor system | |
| JPH01118931A (en) | Program conversion method | |
| US20200409746A1 (en) | Information processing apparatus and recording medium | |
| JPH03122722A (en) | Object program forming system | |
| JP2005332370A (en) | Control device | |
| JPH10111857A (en) | Multi-processor | |
| JPH03250336A (en) | Memory allocation system | |
| JP4122212B2 (en) | Multiprocessor system | |
| JP2000020482A (en) | Loop parallelization method | |
| JP2809073B2 (en) | Array memory allocation method | |
| JP3006505B2 (en) | Apparatus and method for modifying a program including a parallel process, and a storage medium for storing the modified program | |
| JP3072772B2 (en) | Compiling device | |
| JPS62205434A (en) | Compiling processing system for program capable of recursive call | |
| JPS63163636A (en) | Executing system for parallel processing | |
| JPH04107638A (en) | Literal constant allocation system | |
| JPH0991151A (en) | Compiling device and processor device | |
| JPH047748A (en) | Automatic array element assignment processing system based on reference order | |
| JP2001184320A (en) | Distributed execution device and recording medium | |
| Tanus | Exploring parallelism on pure functional languages with ACQuA | |
| JP2000222218A (en) | Compiling device and recording medium |