JP3686261B2 - Computer, program conversion device, and program recording medium - Google Patents

Description

というように記述される計算実行プログラム２２ａは、出現回数の少ないインデックスについてのインデックス用作業配列２３ａ及びオーダ用作業配列２４ａに従って算出式の計算処理を実行する。
【０１２１】
そして、この作業配列作成プログラム３０の作成する作業配列を受けて、例えば、
n=0
do n1=1,kxmax
akkx1n=a(index(n1))
bkkx1n=b(index(n1))
do n2=1,index-new(n1)
if(index-new(n1).ne.0)then
n=n+1
a(n1)=akkx1n+bkkx1n*c(llx(n))
end if
end do
kxmax ：作業配列の行数
llxx：図７（ｂ）の作業配列の値
index-new ：各インデックス毎の出現回数
akkx1n：変数 bkkx1n：変数
というように記述される計算実行プログラム２２ｂは、出現回数の多いインデックスについてのインデックス用作業配列２３ｂ及びオーダ用作業配列２４ｂに従って算出式の計算処理を実行する。
【０１２２】
最終的には、この２つの算出式の計算処理の処理結果を加算することで、算出式の計算結果を得ることになる。
最後に、並列システムへの適用について説明する。
【０１２３】
本発明は、単一プロセッサ構成の計算機にその適用が限られるものではなく、並列プロセッサ構成の計算機にもそのまま適用できる。
並列システムには、図２９（ａ）に示す構成を採る分散メモリ方式のものと、図２９（ｂ）に示す構成を採る共用メモリ方式のものとがあるが、本発明は、そのいずれに対しても適用可能である。
【０１２４】
但し、本発明を分散メモリ方式の並列システムに適用する場合、例えば、プロセッサｉ（ｉ＝０〜ｎ）の実バンクアドレスが「０〜ｍ−１」で説明するならば、プロセッサ０には「０〜ｍ−１」、プロセッサ１には「ｍ〜２×ｍ−１」、プロセッサ２には「２×ｍ〜３×ｍ−１」というように、システム全体に対するアドレスを設定することになる。
【０１２５】
本発明を並列システムに適用する場合、図３に示すインデックス用作業配列２３及びオーダ用作業配列２４の例で説明するならば、図３０に示すように、インデックス用作業配列２３及びオーダ用作業配列２４をプロセッサ数に応じて分割して、それを各プロセッサに配分する構成を採ることになる。また、図３１に示すリストを受けて、図３２に示すようなインデックス用作業配列２３及びオーダ用作業配列２４を作成するときの例で説明するならば、この図３２に示すように、インデックス用作業配列２３及びオーダ用作業配列２４をプロセッサ数に応じて分割して、それを各プロセッサに配分する構成を採ることになる。
【０１２６】
このとき、各プロセッサの負荷の均等化を図るために、図３３に示すように、各プロセッサに配分するインデックスの数が概略均等になるようにと、インデックス用作業配列２３及びオーダ用作業配列２４を分割することが好ましい。ここで、この図３３では、図３４に示すインデックスの並びを持つリストを想定している。
【０１２７】
図示実施例に従って本発明を説明したが、本発明はこれに限定されるものではない。例えば、実施例では、
do j=1,n
a(index(j))=a(index(j))+b(index(j))*c(j)
end do
という算出式を具体例にして本発明を説明したが、本発明の適用対象となる算出式は如何なるものであってもよい。
【０１２８】
【発明の効果】
以上説明したように、本発明によれば、リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するときにあって、同一のメモリバンクに対するアクセスが連続しないようにとリストのインデックスの並びを変更することで、メモリビジーが回避され、その計算処理を高速に実行できるようになる。
【０１２９】
そして、本発明によれば、リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するときにあって、同一のインデックスの指すメモリバンクのデータを定数として設定しつつスカラー演算に従って実行することで、ベクトルメモリアクセスが減少し、その計算処理を高速に実行できるようになる。
【０１３０】
そして、本発明によれば、リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するときにあって、同一のインデックスの出現回数が多いときには、同一のインデックスの指すメモリバンクのデータを定数として設定しつつスカラー演算に従って実行することで、ベクトルメモリアクセスが減少し、その計算処理を高速に実行できるようになるとともに、同一のインデックスの出現回数が多くないときには、同一のメモリバンクに対するアクセスが連続しないようにとリストのインデックスの並びを変更することで、メモリビジーが回避され、その計算処理を高速に実行できるようになる。
【０１３１】
そして、本発明によれば、リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するときにあって、出現回数の多いインデックスについては、同一のインデックスの指すメモリバンクのデータを定数として設定しつつスカラー演算に従って実行することで、ベクトルメモリアクセスが減少し、その計算処理を高速に実行できるようになるとともに、出現回数の少ないインデックスについては、同一のメモリバンクに対するアクセスが連続しないようにとリストのインデックスの並びを変更することで、メモリビジーが回避され、その計算処理を高速に実行できるようになる。
【図面の簡単な説明】
【図１】本発明の原理構成図である。
【図２】本発明の原理構成図である。
【図３】本発明の説明図である。
【図４】本発明の説明図である。
【図５】本発明の説明図である。
【図６】本発明の説明図である。
【図７】本発明の説明図である。
【図８】本発明の説明図である。
【図９】本発明の説明図である。
【図１０】本発明の説明図である。
【図１１】本発明の一実施例である。
【図１２】作業配列作成プログラムの処理フローである。
【図１３】計算変更プログラムの処理フローである。
【図１４】作業配列作成プログラムの処理説明図である。
【図１５】作業配列作成プログラムの処理説明図である。
【図１６】作業配列作成プログラムの処理フローである。
【図１７】計算変更プログラムの処理フローである。
【図１８】作業配列作成プログラムの処理説明図である。
【図１９】本発明の他の実施例である。
【図２０】作業配列作成プログラムの処理フローである。
【図２１】計算変更プログラムの処理フローである。
【図２２】起動プログラムの処理フローである。
【図２３】起動プログラムの処理説明図である。
【図２４】本発明の他の実施例である。
【図２５】作業配列作成プログラムの処理フローである。
【図２６】作業配列作成プログラムの処理フローである。
【図２７】リストの説明図である。
【図２８】作業配列の説明図である。
【図２９】並列システムの説明図である。
【図３０】並列システムへの適用説明図である。
【図３１】リストの説明図である。
【図３２】並列システムへの適用説明図である。
【図３３】並列システムへの適用説明図である。
【図３４】リストの説明図である。
【図３５】従来技術の説明図である。
【図３６】従来技術の説明図である。
【図３７】従来技術の説明図である。
【図３８】従来技術の説明図である。
【図３９】従来技術の説明図である。
【図４０】従来技術の説明図である。
【符号の説明】
１ 計算機
２ プログラム変換装置
１０ａ 作成手段
１１ａ 計算手段
２０ａ 第１の生成手段
２１ａ 第２の生成手段
１０ｂ 作成手段
１１ｂ 計算手段
２０ｂ 第１の生成手段
２１ｂ 第２の生成手段
１２ｂ 第１の作成手段
１２ａ 第２の作成手段
１３ｂ 第１の計算手段
１３ａ 第２の計算手段
１４ 起動手段
１５ｂ 第１の作成手段
１５ａ 第２の作成手段
１６ｂ 第１の計算手段
１６ａ 第２の計算手段[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a computer that executes calculation processing of a prescribed calculation formula by accessing a memory bank pointed to by an index arranged in a list, a program conversion device that generates a program that performs the calculation processing, and realization of the computer In particular, a computer that can execute a calculation process of a calculation formula at high speed, a program conversion device that generates a program that performs the calculation process, and an implementation of the computer The present invention relates to a program recording medium in which a program used for the program is stored.
[0002]
Many iterative calculations appear in science and technology calculations. Here, memory access by reference to the list becomes a bottleneck, and in many cases, sufficient performance cannot be exhibited. This is because the memory bank once accessed is in a busy state for a specified time, and thus the data in the bank cannot be accessed. In addition, since a vector process cannot be performed in a calculation (refer to regression) in which the same list is reproduced during an iterative calculation, the processing performance of the vector computer is greatly reduced. From now on, the construction of technology to solve these problems has been called out.
[0003]
[Prior art]
A calculation process of a specified calculation formula is executed by accessing a memory bank indicated by an index arranged in a list.
[0004]
  In this case, conventionally, the calculation formula calculation process is executed by accessing the memory bank as it is according to the designation of the list.
  That is, for example,
          do j = 1, n
              a (index (j)) = a (index (j)) + b (index (j)) * c (j)
          end do
As shown in FIG. 35A, an index “ind”eIn the case where a list having an arrangement order of “x (j)” is given and the number of memory banks is 8, an index “as shown in FIG. indeThe memory bank indicated by “x (j)” is used. Then, according to the designation of the list, the calculation formula calculation process is executed using these memory banks in the calculation order as shown in FIG.
[0005]
  The calculation order “j” and the index “ind”eThe memory bank pointed to by “x (j)” is defined as a remainder with respect to the number of memory banks of those values.
  Also, an index “ind that fits in the number of memory banks as shown in FIG.eWhen a list having an arrangement order of “x (j)” is given, a memory bank indicated by the calculation order “j” and “ind”eThe configuration is such that the calculation processing of the calculation formula is executed in the calculation order as shown in FIG. 38 using the memory bank indicated by “x (j)”.
[0006]
[Problems to be solved by the invention]
However, according to such conventional technology, when the calculation process of the prescribed calculation formula is executed by accessing the memory bank pointed to by the index arranged in the list, idle time due to memory busy occurs, There is a problem that calculation processing cannot be executed at high speed.
[0007]
In other words, once accessed, the memory bank is in a busy state for a specified time, so if access to the same memory bank continues, idle time due to memory busy occurs, and the calculation process is executed at high speed. There is a problem that it is not possible.
[0008]
In the above example, the number of memory buses is 4 (memory bus 1 in memory banks 1 and 5, memory bus 2 in memory banks 2 and 6, memory bus 3 in memory banks 3 and 7, memory bus 3 in memory banks 4 and 8) Assuming that a memory bank that has been accessed once is in a busy state for 2 clocks, the calculation processing of the calculation formula of FIG. Specifically, the calculation processing of the calculation formula of FIG. 38 is executed in the calculation form as shown in FIG. 40, and it can be seen that the calculation density is very low.
[0009]
The present invention has been made in view of such circumstances, and is for performing calculation processing of a prescribed calculation formula by accessing a memory bank pointed to by an index arranged in a list. Is provided at a high speed, a new program conversion device for generating a program for performing the calculation process, and a new program recording medium storing a program used to realize the computer For the purpose of providing.
[0010]
[Means for Solving the Problems]
1 and 2 illustrate the basic configuration of the present invention.
In the figure, reference numeral 1 denotes a computer having the present invention, which executes calculation processing of a prescribed calculation formula by accessing a memory bank indicated by an index arranged in a list, and 2 has the present invention. A program conversion apparatus, which accesses a memory bank pointed to by an index arranged in a list, compiles or converts a program that executes a calculation process of a specified calculation formula, and develops it on the computer 1.
[0011]
Here, the functions of the computer 1 of the present invention and the program conversion apparatus 2 of the present invention are specifically realized by a program, and this program operates on a memory to realize the present invention. become.
[0012]
The computer 1 whose principle configuration is shown in FIG. 1A includes a creation unit 10a and a calculation unit 11a, and the program conversion apparatus 2 includes a first generation unit 20a and a second generation unit 21a. .
[0013]
The creation means 10a obtains a remainder with respect to the index radix, creates a work array for managing the correspondence between the index and the numerical value defined by the remainder, and manages the correspondence between the index and the index list order. Create a working array to do.
[0014]
  The calculation means 11a uses the calculation of the calculation formula to be calculated as the inner loop and the appearance of a numerical value defined by the remainder.TimesIs reconstructed in the form of an outer loopdo it, Work arrangement created by the creation means 10aBased on the array dataThe calculation formula is calculated by accessing the memory bank.
[0015]
The first generation unit 20 a generates a program that implements the creation unit 10 a and develops it on the computer 1.
The second generation unit 21 a generates a program that realizes the calculation unit 11 a according to the calculation formula to be calculated, and deploys it to the computer 1.
[0016]
In the computer 1 whose principle configuration is illustrated in FIG. 1A configured as described above, if the example using the number of memory banks as the radix is described, the creation unit 10a has the list shown in FIG. Given the above, a work array as shown in FIG. 3 (a) for managing the correspondence between the index and the numerical value defined by the remainder with respect to the radix of the index is created, and the correspondence between the index and the index list arrangement order A work array as shown in FIG. 3B to be managed is created.
[0017]
  The work arrangement shown in FIG. 3A indicates that, for example, in the list shown in FIG. 35A, the index indicating the fourth memory bank appears in the order of “60 → 68 → 76”. The working arrangement shown in FIG. 3 (b) has an index of 60/68/76, which is 21/26 / of the list.2It shows that it appears 9th.
[0018]
  Upon receiving this work arrangement, the calculation means 11a, for example,
          do j = 1, n
              a (index (j)) = a (index (j)) + b (index (j)) * c (j)
          end do
The calculation formula
         do j = 1, kmax-v
     ! ocl novrec
         do i = 1, maxcnt
           if (kkxx-v (i, j) .gt.0) then
           a (kkxx-v (i, j)) = a (kkxx-v (i, j)) + b (kkxx-v (i, j)) * c (llxx-v (i, j))
           end if
         end do
         end do
                    kmax-v: Number of rows in the work array maxcnt: Number of memory banks
                    kkxx-v (i, j): Value of work array in Fig. 3 (a)
                    llxx-v (i, j): Value of work array in Fig. 3 (b)
In this way, the remainder system is the inner loop, and the numerical value specified by the remainder appears.TimesIs reconstructed in the form of an outer loopdo itThen, the calculation formula is calculated by accessing the memory bank in accordance with the calculation order designated by the work array created by the creation means 10a.
[0019]
That is, the list shown in FIG. 35 (a) is converted into a sequence of indexes as shown in FIG. 4, and the calculation formula calculation process is executed according to the calculation order shown in FIG. Thereby, it is executed in the calculation form as shown in FIG. 6, and a very high calculation density can be realized as compared with the case of following the prior art of FIG.
[0020]
In this way, according to the computer 1 whose principle configuration is shown in FIG. 1 (a), by accessing the memory bank pointed to by the index arranged in the list, the calculation process of the prescribed calculation formula is executed. Therefore, the list index list is changed so that accesses to the same memory bank do not continue, so that memory busy is avoided and the calculation process can be executed at high speed.
[0021]
The computer 1 whose principle configuration is illustrated in FIG. 1B includes a creation unit 10b and a calculation unit 11b, and the program conversion apparatus 2 includes a first generation unit 20b and a second generation unit 21b. .
[0022]
  This creation means 10b uses an index and the appearance of an index.TimesA work array for managing the correspondence relationship between the index and the list arrangement order of the index is created.
[0023]
  The calculation means 11b calculates the calculation formula to be calculated as the occurrence of an index.TimesIs the inner loop, the index system is the outer loop, and is reconstructed using a scalar operationdo it, Work arrangement created by the creation means 10bBased on the array dataThe calculation formula is calculated by repeating the scalar calculation.
[0024]
The first generation unit 20 b generates a program that implements the creation unit 10 b and deploys it to the computer 1.
The second generation unit 21 b generates a program that realizes the calculation unit 11 b according to the calculation formula to be calculated, and deploys it to the computer 1.
[0025]
  In the computer 1 whose principle configuration is shown in FIG. 1B configured as described above, when the list shown in FIG.TimesA work array as shown in FIG. 7 (a) for managing the correspondence relationship between the index and the list array order of the index is created as well as a work array as shown in FIG. 7 (b). To do.
[0026]
In the work array shown in FIG. 7A, in the list shown in FIG. 37, index 1 appears 11 times, index 2 appears 8 times, index 3 appears 8 times, index 4 4 indicates that it appears four times. For example, in the work array shown in FIG. 7B, the index 1 is 1/2/3/4/5/6/7/29/30 / It shows that it appears 31st.
[0027]
  Upon receiving this work arrangement, the calculation means 11b, for example,
              do j = 1, n
                  a (index (j)) = a (index (j)) + b (index (j)) * c (j)
              end do
The calculation formula
             n = 0
             do n1 = 1, kxmax
                 akkx1n = a (index (n1))
                 bkkx1n = b (index (n1))
             do n2 = 1, index-new (n1)
                 if (index-new (n1) .ne.0) then
                   n = n + 1
                   a (n1) = akkx1n + bkkx1n * c (llx (n))
                 end if
             end do
                        kxmax: Number of rows in the work array
                        llxx: Value of work array in Fig. 7 (b)
                        index-new: Appearance for each indexTimes
                        akkx1n: Variable bkkx1n: Variable
The appearance of the indexTimesIs the inner loop, the index system is the outer loop, and is reconfigured using a scalar operation that uses the data in the memory bank indicated by the index as a constant.do it, The specified appearance of the work array created by the creation means 10bTimesThe calculation formula is calculated by repeating the scalar calculation according to.
[0028]
That is, the list shown in FIG. 37 is converted into a sequence of indexes as shown in FIG. 8, and this calculation process is the same according to the image of executing the calculation process of the calculation formula in the calculation order as shown in FIG. The data in the memory bank pointed to by the index is set as a constant and executed according to a scalar operation. Thereby, it is executed in the calculation form as shown in FIG. 10, and a very high calculation density can be realized as compared with the case of following the prior art of FIG. Here, in FIG. 10, it is assumed that the calculation process of “a (n1) = akkx1n + bkkx1n * c (llx (n))” is executed four times during one clock.
[0029]
In this way, according to the computer 1 whose principle configuration is shown in FIG. 1B, by accessing the memory bank pointed to by the index arranged in the list, the calculation process of the prescribed calculation formula is executed. Thus, since the data in the memory bank pointed to by the same index is set as a constant and executed according to the scalar operation, the vector memory access is reduced, and the calculation process can be executed at high speed.
[0030]
The computer 1 whose principle configuration is shown in FIG. 2A includes a first creation means 12b, a second creation means 12a, a first calculation means 13b, a second calculation means 13a, and an activation means 14. With.
[0031]
The first creation means 12b corresponds to the creation means 10b included in the computer 1 whose principle configuration is shown in FIG. 1B, and the second creation means 12a is shown in FIG. 1A as the principle configuration. The first calculating means 13b corresponds to the creating means 10a included in the computer 1, the first calculating means 13b corresponds to the calculating means 11b included in the computer 1 whose principle configuration is shown in FIG. 1B, and the second calculating means 13a is 1 (a) corresponds to the calculation means 11a provided in the computer 1 whose principle configuration is illustrated.
[0032]
The activation means 14 selects and activates either the first calculation means 13b or the second calculation means 13a according to the arrangement format of the work arrangement created by the first creation means 12b.
[0033]
  In the computer 1 whose principle configuration is shown in FIG. 2A configured as described above, the first creation unit 12b, when given a list, generates an index and the appearance of the index.TimesA work array for managing the correspondence relationship between the index and the list arrangement order of the index is created.
[0034]
On the other hand, when the second creation unit 12a is activated unconditionally or when the activation unit 14 is activated when a condition for activating the second calculation unit 13a is satisfied and given a list, the second creation unit 12a A remainder is obtained, and a work array for managing the correspondence between the index and the numerical value defined by the remainder is created, and a work array for managing the correspondence between the index and the list arrangement order of the indices is created.
[0035]
  In response to the work sequence created by the first creation means 12b, the activation means 14 causes the appearance of an index with the same work layout.TimesArray format with many(Format of array data)Is displayed, the first calculation means 13b is activated. Otherwise, the second calculation means 13a is activated.
[0036]
  When activated in this way, the first calculation means 13b calculates the calculation formula to be calculated as the occurrence of an index.TimesIs the inner loop, the index system is the outer loop, and is reconstructed using a scalar operationdo it, The specified appearance of the work sequence created by the first creation means 12bTimesThe calculation formula is calculated by repeating the scalar calculation according to.
[0037]
  On the other hand, when activated in this way, the second calculation means 13a uses the calculation of the calculation formula to be calculated as the inner loop and the appearance of a numerical value defined by the remainder.TimesIs reconstructed in the form of an outer loopdo itThe calculation formula is calculated by accessing the memory bank in accordance with the calculation order designated by the work array created by the second creation means 12a.
[0038]
  In this way, according to the computer 1 whose principle configuration is shown in FIG. 2A, by accessing the memory bank pointed to by the index arranged in the list, the calculation process of the prescribed calculation formula is executed. Appearance of the same indexTimesWhen there is a large number, the memory bank data pointed to by the same index is set as a constant and executed according to the scalar operation, thereby reducing vector memory access and enabling the calculation processing to be executed at high speed. Frequency of occurrenceTimesWhen there is not a large number, the list of indexes in the list is changed so that accesses to the same memory bank do not continue, so that memory busy is avoided and the calculation process can be executed at high speed.
[0039]
The computer 1 whose principle configuration is shown in FIG. 2B includes a first creation means 15b, a second creation means 15a, a first calculation means 16b, and a second calculation means 16a.
[0040]
The first creation means 15b corresponds to the creation means 10b included in the computer 1 whose principle configuration is shown in FIG. 1B, and the second creation means 15a is a work arrangement created by the first creation means 15b. 1 corresponds to the creation means 10a included in the computer 1 whose principle configuration is shown in FIG. 1A, and the first calculation means 16b is the same as that shown in FIG. b) corresponds to the calculation means 11b included in the computer 1 whose principle configuration is illustrated, and the second calculation means 16a corresponds to the calculation means 11a included in the computer 1 whose principle configuration is illustrated in FIG.
[0041]
  In the computer 1 whose principle configuration is illustrated in FIG. 2B configured as described above, the first creation unit 15b appears when a list is given.TimesThe index and the appearance of the index, with many indexes as management targetsTimesA work array for managing the correspondence relationship between the index and the list arrangement order of the index is created.
[0042]
On the other hand, when the list is given, the second creating unit 15a obtains a remainder with respect to the radix of the index while managing an index other than the index managed in the work array created by the first creating unit 15b, A work array for managing the correspondence between the index and the numerical value defined by the remainder is created, and a work array for managing the correspondence between the index and the list arrangement order of the index is created.
[0043]
  In response to the creation of the work array created by the first creation means 15b, the first calculation means 16b uses the index managed by the work array as a processing target and calculates the calculation formula to be calculated as an index. The appearance ofTimesIs the inner loop, the index system is the outer loop, and is reconstructed using a scalar operationdo itThe specified occurrence of that working arrayTimesThe calculation formula is calculated by repeating the scalar calculation according to.
[0044]
  On the other hand, in response to the creation of the work array created by the second creation means 15a, the second calculation means 16a uses the index managed by the work array as a processing target to calculate the calculation formula to be calculated. , The remainder system is the inner loop, and the numerical value specified by the remainder appearsTimesIs reconstructed in the form of an outer loopdo itThen, the calculation formula is calculated by accessing the memory bank according to the calculation order designated by the work array.
[0045]
  In this way, according to the computer 1 whose principle configuration is shown in FIG. 2B, by accessing the memory bank pointed to by the index arranged in the list, the calculation process of the prescribed calculation formula is executed. AppearanceTimesFor an index with a large number of indexes, the memory bank data pointed to by the same index is set as a constant and executed according to a scalar operation, thereby reducing vector memory access and allowing the calculation process to be executed at high speed.TimesFor an index with a small number of addresses, memory busy is avoided and the calculation process can be executed at high speed by changing the arrangement of the index in the list so that accesses to the same memory bank do not continue.
[0046]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, the present invention will be described in detail according to embodiments.
FIG. 11 shows an embodiment of a computer 1 having the present invention.
[0047]
The computer 1 of the present invention according to this embodiment realizes the computer 1 of the present invention whose principle configuration is shown in FIG. 1, and creates a work array necessary for calculation processing of a calculation formula to be calculated. Work array creation program 20, calculation change program 21 that changes the program format of the calculation formula to be calculated, calculation execution program 22 created by the calculation change program 21, and index created by the work array creation program 20 A work array 23 and an order work array 24 created by the work array creation program 20 are provided.
[0048]
Here, the calculation execution program 22 is created by the calculation change program 21. At this time, a program (not shown) creates the work array creation program 20 accordingly.
[0049]
The program having the function of creating the work array creation program 20 and the calculation change program 21 are realized by the functions of the program conversion tool and the compiler, but the programmer may code them manually.
[0050]
FIG. 12 shows an example of a processing flow executed by the work array creation program 20 in order to realize the computer 1 of the present invention whose principle configuration is shown in FIG. 1A, FIG. 13 and FIG. An embodiment of a processing flow executed by the calculation change program 21 for realizing the computer 1 of the present invention illustrating the principle configuration is illustrated.
[0051]
Next, processing of the computer 1 of the present invention configured as shown in FIG. 11 will be described according to this processing flow.
When the work array creation program 20 is started, first, in step 1, an index work array 23 and an order work array 24 are defined as shown in the processing flow of FIG. This work array is defined by defining a work array having a size “number of memory banks × sufficient size”.
[0052]
Subsequently, in step 2, the defined work array is cleared to zero. Subsequently, in step 3, the next index (the first index when entering the first process) is extracted from the indexes arranged in the list. That is, one unprocessed index is taken out from the index of the list as shown in FIG.
[0053]
Subsequently, in step 4, it is determined whether or not all indexes have been extracted, and when it is determined that all indexes have not been extracted, the process proceeds to step 5, and the number of memory banks of the indexes extracted in step 3 The memory bank pointed to by the index extracted in step 3 is specified.
[0054]
Subsequently, in step 6, the arrangement order in the list of indexes taken out in step 3 is specified. Subsequently, in step 7, the index extracted in step 3 is stored in the area of the index work array 23 pointed to by the memory bank specified in step 5 in the order of appearance, and the order of the list array specified in step 6 corresponds to the order. After the data is stored in the area of the work array 24, the process returns to step 3.
[0055]
On the other hand, when it is determined in step 4 that all indexes have been extracted, the process proceeds to step 8 where the memory bank in which the index appears most is searched out, the number of occurrences is specified, and the process ends.
[0056]
  In this way, the work array creation program 20 uses the index in the order of the array from the list.deWhen x (i) is extracted, its index indeBy calculating the remainder mod-b for the number of memory banks b of x (i), the index indeThe memory bank indicated by x (i) is obtained and the number of occurrences cnt-b of the memory bank is obtained. As shown in FIG. 14A, the area of the index work array 23 indicated by the memory bank / number of appearances The index indeIn addition to storing x (i), as shown in FIG. 14B, the index in the order work array 24 indicated by the memory bank / number of appearances.deA process of storing the list arrangement order i of x (i) is executed.
[0057]
In this process, in consideration of the fact that the one-dimensional array starts from 1 in the Fortran, the work array creation program 20 reads “mod When b = 0, change it to “mod” b = n (n: number of memory banks) ”.
[0058]
In this manner, when the list shown in FIG. 35A is given, the work array creation program 20 manages the correspondence between the index and the memory bank pointed to by the index as shown in FIG. The work array for order 23 is created, and an order work array 24 as shown in FIG. 3B for managing the correspondence between the index and the list array order of the indexes is created.
[0059]
  In the index work array 23 shown in FIG. 3A, in the list shown in FIG. 35A, for example, the index indicating the fourth memory bank appears in the order of “60 → 68 → 76”. The order work array 24 shown in FIG. 3 (b) has an index of 60/68/76, which is 21/26 /2It shows that it appears 9th.
[0060]
On the other hand, when the calculation change program 21 is started, as shown in the processing flow of FIG. 13, first, in step 1, first, in step 1, the calculation formula loop to be calculated is set in the number of memory banks on the inside, and on the outside. Divide according to the maximum number of occurrences of the index in the memory bank.
[0061]
Subsequently, in step 2, an IF statement that avoids calculation of the blank part of the index work array 23 (order work array 24) is inserted, and in step 3 the index and subscript to be used are changed. In step 4, a calculation execution program 22 is created by inserting a vectorization instruction line (! Ocl novrec) for vectorization of the inner loop.
[0062]
  For example,
          do j = 1, n
              a (index (j)) = a (index (j)) + b (index (j)) * c (j)
          end do
The operation of the calculation formula
         do j = 1, kmax-v
     ! ocl novrec
         do i = 1, maxcnt
           if (kkxx-v (i, j) .gt.0) then
           a (kkxx-v (i, j)) = a (kkxx-v (i, j)) + b (kkxx-v (i, j)) * c (llxx-v (i, j))
           end if
         end do
         end do
                    kmax-v: Number of rows in the work array maxcnt: Number of memory banks
                    kkxx-v (i, j): Value of index work array 23
                    llxx-v (i, j): value of work array 24 for order
Thus, the calculation execution program 22 defined by changing the program format of the calculation formula to be calculated is created.
[0063]
From this point, the calculation execution program 22 is reconfigured so that the calculation formula to be calculated is recalculated in such a manner that the remainder system is the inner loop and the number of occurrences of the numerical value defined by the remainder is the outer loop. The calculation formula is calculated by accessing the memory bank in accordance with the calculation order designated by the (order work array 24).
[0064]
For example, the list shown in FIG. 35A is converted into a sequence of indexes as shown in FIG. 4, and the calculation processing of the calculation formula is executed according to the calculation order shown in FIG.
[0065]
In this way, when following the processing flow of FIG. 12 and FIG. 13, the computer 1 of the present invention executes the calculation processing of the prescribed calculation formula by accessing the memory bank indicated by the index arranged in the list. Thus, a configuration is adopted in which the list index list is changed so that accesses to the same memory bank do not continue. Thereby, memory busy is avoided and the calculation process can be executed at high speed.
In the processing flow of FIG. 12, the work array creation program 20 is configured to create the index work array 23 by obtaining a remainder with respect to the number of index memory banks. However, the work array creation program 20 has a power of 2 smaller than the number of memory banks. It is also possible to adopt a configuration in which the index work array 23 is created by setting a value as a radix and obtaining a remainder for the radix of the index.
[0066]
For example, when the list shown in FIG. 35A is given, if the index work array 23 is created by setting 4 as the radix and obtaining the remainder of the index for the radix, FIG. 3A 15 is created instead of the index work array 23 shown in FIG. 15, the index work array 23 shown in FIG. This is because the arrangement of the indexes shown in FIG.
[0067]
In the processing flow of FIG. 12, the method for obtaining the remainder is not particularly described. However, when a power of 2 is used as the radix, the remainder of the index with respect to the radix is obtained by bit shift processing or bit mask processing. Therefore, the remainder can be easily obtained.
[0068]
For example, an index of 29 is expressed as “00011101” in binary notation, but the remainder for 29 of 8 is “101”, which is the lower 3 bits, so the lower 3 bits are extracted. By using bit shift processing or bit mask processing, the remainder can be easily obtained.
[0069]
In addition, in the processing flow of FIG. 13, a configuration is adopted in which an IF statement that avoids the calculation of the blank part of the index work array 23 (order work array 24) is employed, but the calculation is performed by filling the blank part. By doing so, this IF statement can be omitted. In other words, if the index shown in FIG. 4 is changed, the IF statement can be omitted if the calculation is performed in such a way that the blank portion of the index is filled.
[0070]
In the processing flow of FIG. 12, the index work array 23 and the order work array 24 are defined by the method of “number of memory banks (number of remainders) × sufficient size”, but the radix is set. After that, the number of occurrences of the index is calculated for each residue, the number of occurrences of the residue whose occurrence is not 0 is obtained, and the index work is performed by the method of “the number of residues whose occurrence does not become 0 × maximum occurrence” If the arrangement for defining the array 23 and the order work array 24 is adopted, the index work array 23 and the order work array 24 can be defined with the minimum necessary memory capacity.
[0071]
Although not described in the processing flow of FIG. 12, when a long scientific calculation is performed, a calculation formula described by the calculation execution program 22 is called and calculated many times.
[0072]
In such a case, the work array creation program 20 does not adopt a configuration for generating the index work array 23 and the order work array 24 each time, but changes the list specified in the previous calculation. It is preferable to check whether the index work array 23 and the order work array 24 are generated in accordance with the change only when it is changed.
[0073]
FIG. 16 shows an example of a processing flow executed by the work array creation program 20 for realizing the computer 1 of the present invention whose principle configuration is shown in FIG. 1B, FIG. 17 and FIG. An embodiment of a processing flow executed by the calculation change program 21 for realizing the computer 1 of the present invention illustrating the principle configuration is illustrated.
[0074]
Next, processing of the computer 1 of the present invention configured as shown in FIG. 11 will be described according to this processing flow.
When the work array creation program 20 is started, as shown in the processing flow of FIG. 16, first, in step 1, the maximum index that appears in the list is specified. Subsequently, in step 2, an index work array 23 and an order work array 24 are defined. This work array is defined by defining a work array having a size of “maximum index value × sufficient size”.
[0075]
Subsequently, in step 3, the defined work array is cleared to zero. Subsequently, in step 4, the next index (the first index when starting processing first) is extracted from the indexes arranged in the list. That is, one unprocessed index is taken out from the index of the list as shown in FIG.
[0076]
Subsequently, in step 5, it is determined whether or not all indexes have been extracted. If it is determined that all indexes have not been extracted, the process proceeds to step 6, where the array in the list of indexes extracted in step 4 is displayed. Identify the order. Subsequently, in step 7, the index extracted in step 4 is stored in the area of the index work array 23 indicated by the index extracted in step 4, and the order work array corresponding to the list array order specified in step 6 is stored. After storing in the area 24, the process returns to step 4.
[0077]
On the other hand, when it is determined in step 4 that all indexes have been extracted, the process proceeds to step 8 to search for the most frequently occurring index, specify the number of appearances, and end the process.
[0078]
  In this way, the work array creation program 20 uses the index in the order of the array from the list.deWhen x (i) is extracted, as shown in FIG.dex (i) and its index indeThe number of occurrences of x (i) in the area of the index work array 23 indicated by cnt-mdeIn addition to storing x (i), as shown in FIG.dex (i) and its index indeThe index in the area of the order work array 24 pointed to by the number of occurrences of x (i) cnt-mdeA process of storing the list arrangement order i of x (i) is executed.
[0079]
In this way, when the list shown in FIG. 37 is given, the work array creation program 20 manages the correspondence between the index and the number of appearances of the index as shown in FIG. 7A. And an order work array 24 as shown in FIG. 7B for managing the correspondence between the index and the list arrangement order of the indexes.
[0080]
In the work array shown in FIG. 7A, in the list shown in FIG. 37, index 1 appears 11 times, index 2 appears 8 times, index 3 appears 8 times, index 4 4 indicates that it appears four times. For example, in the work array shown in FIG. 7B, the index 1 is 1/2/3/4/5/6/7/29/30 / It shows that it appears 31st.
[0081]
On the other hand, when the calculation change program 21 is started, as shown in the processing flow of FIG. 17, first, in step 1, the calculation formula loop to be calculated is calculated with the number of indexes on the inner side and the index number on the outer side. Split according to the number of occurrences of.
[0082]
Subsequently, in step 2, an IF statement that avoids calculation of the blank part of the index work array 23 (order work array 24) is inserted, and in step 3 the index and subscript to be used are changed. A calculation execution program 22 according to the form of scalar calculation is created.
[0083]
  For example,
              do j = 1, n
                  a (index (j)) = a (index (j)) + b (index (j)) * c (j)
              end do
The operation of the calculation formula
             n = 0
             do n1 = 1, kxmax
                 akkx1n = a (index (n1))
                 bkkx1n = b (index (n1))
             do n2 = 1, index-new (n1)
                 if (index-new (n1) .ne.0) then
                   n = n + 1
                   a (n1) = akkx1n + bkkx1n * c (llx (n))
                 end if
             end do
                        kxmax: Number of rows in the work array
                        llxx: Value of work array in Fig. 7 (b)
                        index-new: Appearance for each indexTimes
                        akkx1n: Variable bkkx1n: Variable
Thus, the calculation execution program 22 defined by changing the program format of the calculation formula to be calculated is created.
[0084]
Thus, the calculation execution program 22 is reconfigured in a format that uses a scalar operation in which the number of occurrences of the index to be calculated is the inner loop, the index system is the outer loop, and the data in the memory bank indicated by the index is a constant. Then, by repeating the scalar calculation according to the number of appearances specified by the index work array 23 (order work array 24), the calculation formula is calculated.
[0085]
For example, the list shown in FIG. 37 is converted into a sequence of indexes as shown in FIG. 8, and the calculation processing of the calculation formula is executed in accordance with the calculation order shown in FIG.
[0086]
In this way, when following the processing flow of FIG. 16 and FIG. 17, the computer 1 of the present invention executes the calculation processing of the prescribed calculation formula by accessing the memory bank indicated by the index arranged in the list. Therefore, a configuration is adopted in which data in the memory bank pointed to by the same index is set as a constant and executed according to a scalar operation. As a result, vector memory access is reduced, and the calculation process can be executed at high speed.
[0087]
The index work array 23 created in the processing flow of FIG. 16 is configured to take a configuration in which each index in the list is compared with the index positioned in the front, and when the index is small, the order is moved forward. It is also possible to create by using the sorting method (diamond sort method).
[0089]
Further, in the processing flow of FIG. 16, the index work array 23 and the order work array 24 are defined by the method of “maximum index value × sufficient size”, but the number of appearances of each index is obtained. , When the configuration in which the index work array 23 and the order work array 24 are defined by the method of “the number of indexes where the number of appearances does not become 0 × the maximum number of appearances” is adopted, the index work array with the minimum necessary memory capacity. 23 and the order work array 24 can be defined.
[0090]
Further, although not described in the processing flow of FIG. 16, when a long scientific calculation is performed, a calculation formula described in the calculation execution program 22 is called and calculated many times.
[0091]
In such a case, the work array creation program 20 changes the list specified at the time of the previous calculation, rather than adopting a configuration for generating the index work array 23 and the order work array 24 each time. It is preferable to check whether or not the index work array 23 and the order work array 24 are generated in accordance with the change only when it is changed.
[0092]
FIG. 19 shows another embodiment of the computer 1 having the present invention.
The computer 1 of the present invention according to this embodiment realizes the computer 1 of the present invention whose principle configuration is shown in FIG. 2, and creates a work array necessary for calculation processing of a calculation formula to be calculated. Work sequence creation program 30, calculation change program 31 for changing the program format of the calculation formula to be calculated, startup program 32 for starting the calculation execution programs 22a and 22b, and calculation execution program created by the calculation change program 31 22a, b, index work arrays 23a, b created by the work array creation program 30, and order work arrays 24a, b created by the work array creation program 30.
[0093]
Here, the calculation execution programs 22a and 22b are created by the calculation change program 31. At this time, a program (not shown) creates the work array creation program 30 accordingly.
[0094]
The program having the function of creating the work array creation program 30 and the calculation change program 31 are realized by the functions of the program conversion tool and the compiler, but the programmer may code them manually.
[0095]
FIG. 20 shows an example of a processing flow executed by the work array creation program 30 in order to realize the computer 1 of the present invention whose principle configuration is shown in FIG. 2A, FIG. 21 and FIG. An example of a processing flow executed by the calculation change program 31 to realize the computer 1 of the present invention illustrating the principle configuration, FIG. 22 shows the computer 1 of the present invention illustrating the principle configuration in FIG. An example of a processing flow executed by the activation program 32 to realize it is illustrated.
[0096]
  Next, processing of the computer 1 of the present invention configured as shown in FIG. 19 will be described according to this processing flow.
  When the work array creation program 30 is started, as shown in the process flow of FIG. 20, first, in step 1, according to the process flow of FIG.deWhen x (i) is extracted, its index indeBy calculating the remainder mod-b for the number of memory banks b of x (i), the index indeThe memory bank indicated by x (i) is obtained and the number of occurrences cnt-b of the memory bank is obtained. As shown in FIG. 14A, the area of the index work array 23 indicated by the memory bank / number of appearances The index indeIn addition to storing x (i), as shown in FIG. 14B, the index in the order work array 24 indicated by the memory bank / number of appearances.deBy storing the list arrangement order i of x (i), the index work array 23a and the order work array 24a are created.
[0097]
  Subsequently, in step 2, according to the processing flow of FIG.deWhen x (i) is extracted, as shown in FIG.dex (i) and its index indeThe number of occurrences of x (i) in the area of the index work array 23 indicated by cnt-mdeIn addition to storing x (i), as shown in FIG.dex (i) and its index indeThe index in the area of the order work array 24 pointed to by the number of occurrences of x (i) cnt-mdeBy storing the list arrangement order i of x (i), the index work array 23b and the order work array 24b are created.
[0098]
  On the other hand, as shown in the processing flow of FIG. 21, the calculation change program 31 first starts at step 1 according to the processing flow of FIG.
          do j = 1, n
              a (index (j)) = a (index (j)) + b (index (j)) * c (j)
          end do
The operation of the calculation formula
         do j = 1, kmax-v
     ! ocl novrec
         do i = 1, maxcnt
           if (kkxx-v (i, j) .gt.0) then
           a (kkxx-v (i, j)) = a (kkxx-v (i, j)) + b (kkxx-v (i, j)) * c (llxx-v (i, j))
           end if
         end do
         end do
                    kmax-v: Number of rows in the work array maxcnt: Number of memory banks
                    kkxx-v (i, j): value of the index work array 23a
                    llxx-v (i, j): value of the work array for order 24a
In this way, the calculation execution program 22a is created that is defined by changing the program format of the calculation formula to be calculated.
[0099]
  Subsequently, in step 2, according to the processing flow of FIG.
              do j = 1, n
                  a (index (j)) = a (index (j)) + b (index (j)) * c (j)
              end do
The operation of the calculation formula
             n = 0
             do n1 = 1, kxmax
                 akkx1n = a (index (n1))
                 bkkx1n = b (index (n1))
             do n2 = 1, index-new (n1)
                 if (index-new (n1) .ne.0) then
                   n = n + 1
                   a (n1) = akkx1n + bkkx1n * c (llx (n))
                 end if
             end do
                        kxmax: Number of rows in the work array
                        llxx: Value of work array in Fig. 7 (b)
                        index-new: Appearance for each indexTimes
                        akkx1n: Variable bkkx1n: Variable
Thus, the calculation execution program 22b defined by changing the program format of the calculation formula to be calculated is created.
[0100]
On the other hand, when the activation program 32 is activated, as shown in the processing flow of FIG. 22, first, in step 1, the index work array 23b created by the work array creation program 30 appears in the same index. It is determined whether or not an array format with a large number of times is indicated.
[0101]
For example, as shown in FIG. 23, this determination process compares the number of indexes m registered in the index work array 23b with the maximum number of occurrences n of the index registered in the index work array 23b. When “n> m”, it is determined that the index work array 23b indicates an array format in which the same index appears frequently, and when “m> n”, it is determined that this is not the case.
[0102]
When it is determined in step 1 that the index work array 23b indicates an array format in which the same index appears frequently, the process proceeds to step 2 to start the calculation execution program 22b.
[0103]
When started in this way, the calculation execution program 22b sets the number of occurrences of the index to be calculated as the inner loop, sets the index system as the outer loop, and uses scalar calculation with the data in the memory bank indicated by the index as a constant. The calculation formula is calculated by repeating the scalar operation according to the number of appearances specified by the index work array 23b (order work array 24b).
[0104]
For example, the list shown in FIG. 37 is converted into a sequence of indexes as shown in FIG. 8, and the calculation processing of the calculation formula is executed in accordance with the calculation order shown in FIG.
[0105]
On the other hand, when it is determined in step 1 that the index work array 23b does not indicate an array format in which the same index appears frequently, the process proceeds to step 3 to start the calculation execution program 22a.
[0106]
When started in this way, the calculation execution program 22a is reconfigured so that the calculation formula to be calculated is calculated with the remainder system as the inner loop and the number of occurrences of the numerical value defined by the remainder as the outer loop. Thus, the calculation formula is calculated by accessing the memory bank in accordance with the calculation order designated by the index work array 23a (order work array 24a).
[0107]
For example, the list shown in FIG. 35A is converted into a sequence of indexes as shown in FIG. 4, and the calculation processing of the calculation formula is executed according to the calculation order shown in FIG.
[0108]
In this way, in the computer 1 having the present invention shown in FIG. 19, in the case where the same index appears frequently, the calculation formula is calculated using the index work array 23b and the order work array 24b. If the list is a list in which the same index does not frequently appear, the calculation formula is calculated at high speed by executing the calculation processing of the calculation formula using the index work array 23a and the order work array 24a. It is processed like this.
[0109]
In the embodiment shown in FIG. 19, the index work array 23a and b and the order work array 24a and b are created in advance. First, the index work array 23b and the order work array 24b are created. It is also possible to adopt a method of determining whether or not to create the index work array 23a and the order work array 24a according to the created array format.
[0110]
According to this method, when it is not necessary to create the index work array 23a and the order work array 24a, it is not necessary to create them.
FIG. 24 shows an embodiment of the computer 1 equipped with the present invention for realizing this method.
[0111]
In order to realize this method, the startup program 32 prepared in the embodiment of FIG. 19 is omitted, and the work sequence creation program 30 executes the processing flow shown in FIG.
[0112]
That is, in order to realize this method, the work array creation program 30 first, as shown in the process flow of FIG. 25, first, in step 1, according to the process flow of FIG. A work array 24b is created. Subsequently, in step 2, it is determined whether or not the created index work array 23b indicates an array format in which the same index appears frequently.
[0113]
When it is determined in this determination process that the array format in which the same index appears frequently is not indicated, the process proceeds to step 3 and the index work array 23a and the order work array are performed according to the processing flow of FIG. 24a is created, and in the subsequent step 4, the calculation execution program 22a is started, and when it is determined that an array format having the same number of occurrences of the same index is indicated, the process proceeds to step 5 to The calculation execution program 22b is activated without creating the work array 23a and the order work array 24a.
[0114]
In the above-described embodiments of FIG. 19 and FIG. 24, the configuration is such that either the calculation execution program 22a or the calculation execution program 22b is started. However, the index arranged in the list has a large number of appearances. The index work array 23b and the order work array 24b are created by using an index with a large number of appearances as a management target, and the index work array 23a and the order work array 24a with a low appearance number as a management target. For an index with a small number of appearances, the calculation execution program 22a executes a calculation formula calculation process according to the index work array 23a and the order work array 24a. Calculation execution program 22b is indexed That executes the calculation processing of the calculation formula according to use work array 23b and orders for work array 24b, it is also possible to adopt a method for illustrating the basic configuration in FIG. 2 (b).
[0115]
According to this method, when an index with a large number of appearances and an index with a small number of appearances coexist, the calculation process of the calculation formula can be executed at high speed.
[0116]
FIG. 26 shows an example of a processing flow executed by the work array creation program 30 to realize this method.
When realizing this method, the work array creation program 30 first, as shown in the process flow of FIG. 26, first, in step 1, according to the process flow of FIG. 16, the index work array 23b and the order work The array 24b is created.
[0117]
Subsequently, in step 2, an index with a small number of appearances is identified according to the created index work array 23b, and the data of the identified index is deleted from the created index work array 23b and the order work array 24b. As a result, the index work array 23b and the order work array 24b are created for indexes with a large number of appearances.
[0118]
Subsequently, in step 3, by using the deleted index as a management target, the index work array 23a and the order work array 24a are created according to the processing flow of FIG. 23a and an order work array 24a are created.
[0119]
In this way, in the case of following the processing flow of FIG. 26, the work array creation program 30, for example, given a list as shown in FIG. In addition, an index work array 23b according to the array format shown in FIG. 7A is created, and an order work array 24b according to the array format shown in FIG. 7B is created. 28 (b), an index work array 23a is created in accordance with the array format shown in FIG. 3 (a), and an order work array 24a is created in accordance with the array format shown in FIG. 3 (b). To do.
[0120]
In response to the work sequence created by the work sequence creation program 30, for example,

The calculation execution program 22a described as described above executes the calculation processing of the calculation formula according to the index work array 23a and the order work array 24a for the index with a small number of appearances.
[0121]
  In response to the work sequence created by the work sequence creation program 30, for example,
             n = 0
             do n1 = 1, kxmax
                 akkx1n = a (index (n1))
                 bkkx1n = b (index (n1))
             do n2 = 1, index-new (n1)
                 if (index-new (n1) .ne.0) then
                   n = n + 1
                   a (n1) = akkx1n + bkkx1n * c (llx (n))
                 end if
             end do
                        kxmax: Number of rows in the work array
                        llxx: Value of work array in Fig. 7 (b)
                        index-new: Appearance for each indexTimes
                        akkx1n: Variable bkkx1n: Variable
The calculation execution program 22b described as described above executes the calculation processing of the calculation formula according to the index work array 23b and the order work array 24b for the index having a large number of appearances.
[0122]
Ultimately, the calculation results of the calculation formulas are obtained by adding the processing results of the calculation processes of the two calculation formulas.
Finally, application to a parallel system will be described.
[0123]
The application of the present invention is not limited to a computer having a single processor configuration, but can be applied to a computer having a parallel processor configuration as it is.
There are two types of parallel systems: a distributed memory system adopting the configuration shown in FIG. 29 (a) and a shared memory system adopting the configuration shown in FIG. 29 (b). Is applicable.
[0124]
However, when the present invention is applied to a distributed memory parallel system, for example, if the real bank address of the processor i (i = 0 to n) is described as “0 to m−1”, the processor 0 has “ 0 to m−1 ”,“ m to 2 × m−1 ”for the processor 1, and“ 2 × m to 3 × m−1 ”for the processor 2 are set. .
[0125]
When the present invention is applied to a parallel system, the example of the index work array 23 and the order work array 24 shown in FIG. 3 will be described. As shown in FIG. 30, the index work array 23 and the order work array 24 24 is divided according to the number of processors, and the configuration is distributed to each processor. Further, in the case of receiving the list shown in FIG. 31 and creating the index work array 23 and the order work array 24 as shown in FIG. 32, as shown in FIG. 32, as shown in FIG. The work array 23 and the order work array 24 are divided according to the number of processors, and the configuration is distributed to each processor.
[0126]
At this time, in order to equalize the load on each processor, as shown in FIG. 33, the index work array 23 and the order work array 24 are set so that the number of indexes distributed to each processor is approximately equal. Is preferably divided. Here, in FIG. 33, a list having the sequence of indexes shown in FIG. 34 is assumed.
[0127]
  Although the present invention has been described with reference to the illustrated embodiments, the present invention is not limited thereto. For example, in the example:
              do j = 1, n
                  a (index (j)) = a (index (j)) + b (index (j)) * c (j)
              end do
Although the present invention has been described using the calculation formula as a specific example, any calculation formula to which the present invention is applied may be used.
[0128]
【The invention's effect】
As described above, according to the present invention, by accessing the memory bank indicated by the index arranged in the list, access to the same memory bank can be performed when executing the calculation process of the prescribed calculation formula. By changing the list order of the list so that it is not continuous, memory busy is avoided and the calculation process can be executed at high speed.
[0129]
According to the present invention, when the calculation processing of the prescribed calculation formula is executed by accessing the memory bank indicated by the index arranged in the list, the data of the memory bank indicated by the same index is constant. By executing according to the scalar operation while setting as, vector memory access is reduced, and the calculation process can be executed at high speed.
[0130]
  According to the present invention, the access to the memory bank pointed to by the index arranged in the list is performed when the calculation process of the prescribed calculation formula is executed, and the appearance of the same indexTimesWhen there is a lot of data, the data in the memory bank pointed to by the same index is set as a constant and executed according to a scalar operation. Appearance ofTimesWhen there is not a large number, the list of indexes in the list is changed so that accesses to the same memory bank do not continue, so that memory busy is avoided and the calculation process can be executed at high speed.
[0131]
  Then, according to the present invention, when the calculation process of the prescribed calculation formula is executed by accessing the memory bank indicated by the index arranged in the list,TimesFor an index with a large number of indexes, the memory bank data pointed to by the same index is set as a constant and executed according to a scalar operation, thereby reducing vector memory access and allowing the calculation process to be executed at high speed.TimesFor an index with a small number of addresses, memory busy is avoided and the calculation process can be executed at high speed by changing the arrangement of the index in the list so that accesses to the same memory bank do not continue.
[Brief description of the drawings]
FIG. 1 is a principle configuration diagram of the present invention.
FIG. 2 is a principle configuration diagram of the present invention.
FIG. 3 is an explanatory diagram of the present invention.
FIG. 4 is an explanatory diagram of the present invention.
FIG. 5 is an explanatory diagram of the present invention.
FIG. 6 is an explanatory diagram of the present invention.
FIG. 7 is an explanatory diagram of the present invention.
FIG. 8 is an explanatory diagram of the present invention.
FIG. 9 is an explanatory diagram of the present invention.
FIG. 10 is an explanatory diagram of the present invention.
FIG. 11 shows an embodiment of the present invention.
FIG. 12 is a processing flow of a work array creation program.
FIG. 13 is a processing flow of a calculation change program.
FIG. 14 is a process explanatory diagram of a work array creation program.
FIG. 15 is a process explanatory diagram of a work array creation program.
FIG. 16 is a processing flow of a work array creation program.
FIG. 17 is a processing flow of a calculation change program.
FIG. 18 is a process explanatory diagram of a work array creation program.
FIG. 19 is another embodiment of the present invention.
FIG. 20 is a processing flow of a work array creation program.
FIG. 21 is a processing flow of a calculation change program.
FIG. 22 is a processing flow of an activation program.
FIG. 23 is an explanatory diagram of processing of a startup program.
FIG. 24 is another embodiment of the present invention.
FIG. 25 is a processing flow of a work array creation program.
FIG. 26 is a processing flow of a work array creation program.
FIG. 27 is an explanatory diagram of a list.
FIG. 28 is an explanatory diagram of a work arrangement.
FIG. 29 is an explanatory diagram of a parallel system.
FIG. 30 is an explanatory diagram of application to a parallel system.
FIG. 31 is an explanatory diagram of a list.
FIG. 32 is an explanatory diagram of application to a parallel system.
FIG. 33 is an explanatory diagram of application to a parallel system.
FIG. 34 is an explanatory diagram of a list.
FIG. 35 is an explanatory diagram of a prior art.
FIG. 36 is an explanatory diagram of the prior art.
FIG. 37 is an explanatory diagram of the prior art.
FIG. 38 is an explanatory diagram of a prior art.
FIG. 39 is an explanatory diagram of the prior art.
FIG. 40 is an explanatory diagram of the prior art.
[Explanation of symbols]
1 computer
2 Program converter
10a Creation means
11a Calculation means
20a First generation means
21a Second generation means
10b Creation means
11b Calculation means
20b First generation means
21b Second generation means
12b First creation means
12a Second creation means
13b First calculation means
13a Second calculation means
14 Starting means
15b First creation means
15a Second creation means
16b First calculation means
16a Second calculation means

Claims (16)

In the computer that executes the calculation process of the specified calculation formula by accessing the memory bank pointed to by the index arranged in the list,
A first work array for obtaining a remainder with respect to the radix of the index and managing a correspondence between the index and a numerical value defined by the remainder is created, and a second for managing the correspondence between the index and the list arrangement order of the index and creating means for creating a work array,
The operation of the above calculation formula, the coset is the inner loop, the number of occurrences of the numbers defining the remainder was reconstituted in the form of an outer loop, the first and second working sequence to create the creating means Comprising calculating means for calculating the calculation formula by accessing the memory bank based on the array data ,
A featured calculator. The computer according to claim 1, wherein
The creation means uses the number of memory banks as a radix, or uses a value of a power of 2 smaller than the number of memory banks as a radix.
A featured calculator. The computer according to claim 1 or 2,
The creation means obtains a remainder for the index radix according to a logical operation.
A featured calculator. In the computer in any one of Claims 1-3 ,
It said computing means to perform the calculation processing while skipping the blank portion with the said first and second working sequence to create the creation means,
A featured calculator. In the computer that executes the calculation process of the specified calculation formula by accessing the memory bank pointed to by the index arranged in the list,
Creating means for creating a first work array for managing the correspondence between the index and the number of occurrences of the index, and creating a second work array for managing the correspondence between the index and the list arrangement order of the index;
The operation of the above calculation formula, and the number of occurrences of the index and the inner loop, as well as an index based outer loop, and reconstituted in a format using a scalar operations, the first and second work of creating the creation means Comprising calculating means for calculating the calculation formula by repeating the scalar calculation based on the array data of the array ,
A featured calculator. The computer according to claim 5 , wherein
The creation means creates the first work array for managing the correspondence between the index and the number of appearances of the index using a sorting method.
A featured calculator. In the computer in any one of Claims 1-6,
Said creating means, in the case where the calculation formula is iterative calculation, when there is no change in the list, the task sequence dealing with the first and second work array already prepared to be effective That you do n’t want to create
A featured calculator. In the computer in any one of Claims 1-7,
It said creating means, prior to creation of the first and second working sequence, that seek the magnitude of the working sequences, which secures an area of the working sequence in response,
A featured calculator. In the computer in any one of Claims 1-8,
When the computer is composed of a plurality of processors, to be configured to create the first and second working sequence of the creation means are distributed is divided into each processor,
A featured calculator. In the computer that executes the calculation process of the specified calculation formula by accessing the memory bank pointed to by the index arranged in the list,
First creation means for creating a first work array for managing the correspondence between the index and the number of occurrences of the index and creating a second work array for managing the correspondence between the index and the list array order of the index When,
A fourth work sequence for managing the correspondence between the index and the list arrangement order of the index is created while obtaining a remainder with respect to the radix of the index and creating a third work array for managing the correspondence between the index and the numerical value defined by the remainder . A second creation means for creating a work array of
Provided in association with the first and second work arrangements created by the first creation means, and the calculation formula is operated with the number of occurrences of the index as an inner loop and the index system as an outer loop. reconfigures the format using a scalar operations, and a first calculating means for calculating the calculation formula by repeating the scalar operations on the basis of the sequence data the working sequence,
Provided in correspondence to the third and fourth working sequence to create the second creating means, the calculation of the calculation formula, the residue system with inner loop, the outer the number of occurrences of the numbers defining the remainder It was reconstituted in the form of a loop, and the second calculating means for calculating the calculation formula by accessing the memory bank based on the sequence data of the working sequence,
Starting means for selecting and activating either the first calculation means or the second calculation means in accordance with the array data of the first work sequence created by the first creation means. ,
A featured calculator. The computer according to claim 10, wherein
It said second creating means, when the condition that the second calculation means is activated by said activation means is established, that the process to create the third and fourth work sequences,
A featured calculator. In the computer that executes the calculation process of the specified calculation formula by accessing the memory bank pointed to by the index arranged in the list,
More index of appearance times as managed, index and thereby create a first working sequence for managing the correspondence between the number of occurrences of the index, the index and the second managing the correspondence between the list sequence order of the indexes A first creation means for creating a work array;
Using an index other than the index managed by the first and second work arrays created by the first creating means as a management target, a remainder with respect to the radix of the index is obtained, and an index and a numerical value defined by the remainder thereby creating a third work array for managing a correspondence relationship, and second generation means for generating a fourth work array for managing the correspondence between the list sequence order of the indexes and index,
With the index managed by the first and second work arrays created by the first creation means as a processing target, the calculation formula is calculated with the number of occurrences of the index as the inner loop, and the index system as the outer loop. as well as a first calculation means by reconstructing a format using a scalar operation, for calculating the calculation formula by repeating the scalar operations on the basis of the sequence data the working sequence,
As a processing index object to be managed in the third and fourth working sequence to create the second creating means, the calculation of the calculation formula, the residue system with inner loop, the number of occurrences of the numbers defining the remainder the was reconstituted in the form of an outer loop, further comprising a second calculating means for calculating the calculation formula by accessing the memory bank based on the sequence data of the working sequence,
A featured calculator. A program conversion device that compiles or converts a program that executes a calculation process of a specified calculation formula by accessing a memory bank indicated by an index arranged in a list,
A first work array for obtaining a remainder with respect to the radix of the index and managing a correspondence between the index and a numerical value defined by the remainder is created, and a second for managing the correspondence between the index and the list arrangement order of the index First generation means for generating a program for performing a process of creating the work array;
The operation of the above calculation formula, the coset is the inner loop, the number of occurrences of the numbers defining the remainder was reconstituted in the form of an outer loop, the first and second working sequence to create the creating means Comprising a second generation means for generating a program for performing a process of calculating the calculation formula by accessing the memory bank based on the array data .
A program conversion device. A program conversion device that compiles or converts a program that executes a calculation process of a specified calculation formula by accessing a memory bank indicated by an index arranged in a list,
A program that creates a first work array that manages the correspondence between an index and the number of occurrences of the index, and that creates a second work array that manages the correspondence between the index and the list array order of the index. First generating means for generating;
The operation of the above calculation formula, and the number of occurrences of the index and the inner loop, as well as an index based outer loop, and reconstituted in a format using a scalar operations, the first and second work of creating the creation means Second generation means for generating a program for performing processing for calculating the calculation formula by repeating the scalar calculation based on the array data of the array ,
A program conversion device. A program recording medium storing a program used to realize a computer that executes a calculation process of a specified calculation formula by accessing a memory bank indicated by an index arranged in a list,
A first work array for obtaining a remainder with respect to the radix of the index and managing a correspondence between the index and a numerical value defined by the remainder is created, and a second for managing the correspondence between the index and the list arrangement order of the index and the creation process of creating a work array,
The operation of the above calculation formula, the coset is the inner loop, the number of occurrences of the numbers defining the remainder was reconstituted in the form of an outer loop, the first and second working sequence to create the creation process A program for causing a computer to execute a calculation process for calculating the above calculation formula by accessing a memory bank based on array data is stored.
A program recording medium. A program recording medium storing a program used to realize a computer that executes a calculation process of a specified calculation formula by accessing a memory bank indicated by an index arranged in a list,
Creating a first work array that manages the correspondence between the index and the number of occurrences of the index, and creating a second work array that manages the correspondence between the index and the list array order of the index;
The first and second operations of creating the creation process are performed by reconstructing the calculation formula using the index appearance count as an inner loop and the index system as an outer loop and using a scalar calculation. Storing a program for causing a computer to execute a calculation process for calculating the calculation formula by repeating the scalar calculation based on the array data of the array ,
A program recording medium.

Images