並行處理方法中的作業分配方法及並行處理方法
2023-04-29 17:21:21 2
專利名稱：並行處理方法中的作業分配方法及並行處理方法
技術領域：
本發明涉及利用由主計算機和通過共用總線與該主計算機連接的多個處理器構成的計算機系統，由多個處理器並行處理多個作業的並行處理方法中的作業分配方法。另外，涉及用以高速處理大規模的具有特定對稱性的矩陣元素計算，尤其是採用非經驗分子軌道法的分子模擬中的福克矩陣元素計算的並行處理方法。
背景技術：
化學領域中，作為用數值解析分子的狀態和運動的方法，有分子軌道法、分子動力學法、蒙特卡洛法等。其中，非經驗分子軌道計算法是基於第一原理的量子力學的計算，其目的為記述分子中電子的運動。因而，該方法是用於以分子模擬為基礎，詳細解析物質構造和化學反應的工業上重要的方法。
非經驗分子軌道計算法中，將以構成分子的原子的原子核和軌道電子之間距離的2次方乘以經驗常數後的數作為指數的指數函數的倒數或它們的線性組合作為基底函數，相對於一個原子準備多個該基底函數。用這些基底函數的線性組合記述分子內軌道電子的波函數即分子軌道。
確定分子軌道中基底函數的線性組合係數是非經驗分子軌道計算法中的主要處理，該計算必須有與基底函數的數的4次方成比例的計算量和存儲容量。因此，當前的非經驗分子軌道計算法僅僅適用於100原子左右規模的分子體系。為了使生命現象/化學現象的分子論的解釋更加現實，必須開發可適用於數千原子規模的分子體系的非經驗分子軌道計算專用的計算系統。
作為這樣大規模的非經驗分子軌道計算專用的計算系統的例子，有文獻1(白川他「超高速分子軌道計算專用機MOE的體系結構」，電子情報通信學會技術報告，vol.CPSY96-46，no.5，pp.45-50，l996)或文獻2(稻 他，「PPRAM-MOE分子軌道計算專用伺服器MOE的處理節點LSI」，電子情報通信學會技術報告，vol.CPSY98-21，no.4，pp.77-84，1998)中記載的系統。
這些文獻記載的計算系統是將主計算機和例如100個處理器(以下的說明中將用於該並行處理的處理器稱為處理單元)通過共用總線連接而構成的並行處理系統，其目的為高速進行非經驗分子軌道計算。
由於這些系統的各個並行處理單元具有高的運算處理能力且可實現整個系統的低成本，因而能夠提供性價比良好的計算系統。
象非經驗分子軌道計算這樣的計算量大的場合，有效運用並行處理用的多個處理單元以實現進一步高速化是很重要的。特別是在上述文獻記載的系統中，由於在各處理單元通過共用總線和主計算機通信、進行必要的數據收發的同時進行計算處理，因而儘可能減少各處理單元中通信的等待時間以進行有效處理對於高速處理顯得尤為重要。
但是，單純的非經驗分子軌道計算中，在形成作業並分配給並行處理單元的場合，由於各個作業的計算量(計算時間和通信量)不同，因而產生通信的系統開銷(等待時間)，導致無法提高與處理單元的個數成比例的處理性能的問題。
如果進行並行處理的處理單元的個數增加，則主計算機和處理單元之間收發的總數據量雖然不變，但是處理單元的處理能力隨個數成比例增加。結果，一定時間內必須進行通信的量(平均通信量)增加，處理單元數若超過某一個數，則平均通信量超過通信網的處理能力(通信性能)。該情況是發生通信的系統開銷的一個原因。
另外，在短時間內集中發生通信請求、總通信量在某一時刻超過通信網的通信性能，即發生在時間上不均一的通信負荷的場合時，發生通信的開銷，導致並行處理效率的劣化。這在平均通信量不超過通信網的通信性能的場合時也會發生。
從而，為了用並行計算機進行有效的處理，必須減少發生的總通信量並使通信負荷的發生在時間上均一(通信負荷隨時間分散)。
例如，多個作業中的各個作業如果是計算量(計算時間；另外，該計算中包含使用例如ROM(只讀存儲器)的變換處理等。本說明書中的計算和運算同義)和通信量(通信時間)均等的作業，則通過向各處理單元分配作業使經由共用總線進行的通信時刻延遲，從而不發生通信的開銷，可進行並行處理。
文獻3(特開平5-324581號公報)中公開了在並行處理多體問題的計算時使計算負荷均一化的負荷分散方法。該文獻3記載的負荷分散方法中，以各作業的大小完全相等為前提，通過向處理單元分配個數均等的作業，使計算負荷均等。
但是，非經驗分子軌道計算中，各作業的計算循環的次數不同，且從主計算機取得的數據量的差異引起的通信量也不同。從而有僅僅通過使作業個數均等無法使計算負荷均等的問題。
除了上述文獻，文獻4(特開平6-35870號公報)、文獻5(特開平6-243112號公報)、文獻6(特開平7-295942號公報)、文獻8(特開平8-185377號公報)、文獻9(特開平10-240698號公報)等也公開了由多個處理單元進行並行處理時的負荷分散方法。
但是，由於這些文獻4、文獻5、文獻6、文獻7、文獻9記載的任何一個負荷分散方法都是在測定或預測處理單元的負荷狀態的基礎上進行作業的調度，因而必須設置用於測定或預測的專用功能且為了進行測定或預測需要進行附加處理。
另外，文獻8記載的分散計算系統中雖然公開了將分散系統分成具有均等能力的群、以群單位進行負荷分散的方法，但是由於沒有考慮關於通信負荷的分散，有可能導致通信的開銷增大的問題。
針對上述的問題點，本發明的目的為提供即使在各個作業的計算負荷和通信負荷的大小不同的場合，也不用設置專用機構，可以用簡單的方法使負荷均等化的作業分配方法，可進行有效的並行處理，縮短整個系統的處理時間。發明的公開第1發明的並行處理方法中的作業分配方法的特徵在於在利用由主計算機和通過共用總線與該主計算機連接的多個處理器構成的計算機系統，將由所述主計算機與所述處理器之間的通信處理和所述處理器中的運算處理組成的多個作業通過所述多個處理器進行並行處理的並行處理方法中，向所述各處理器分配各作業，使所述作業的通信時間與運算時間之比的平均值為規定值。
根據上述構成的第1發明，由於向多個處理器分配作業使得作業的通信時間與運算時間之比的平均值為規定值，因而通信處理和運算處理都可有效進行，能夠縮短到處理結束為止的時間。
第2發明的特徵為在第1發明的並行處理方法中的作業分配方法中，所述多個作業的全體通信時間與向所述多個處理器均等分配所述多個作業時的一個作業內的運算時間的總和大致相等時，向所述各個處理器分配各作業，使得所述作業的通信時間與運算時間之比的平均值為所述處理器個數的倒數。
根據該第2發明，由於在多個作業的全體通信時間與向多個處理器均等分配多個作業時的一個作業內的運算時間的總和大致相等時，作業的通信時間與運算時間之比的平均值為處理器個數的倒數，因而不會產生各處理器即不通信又不運算的時間帶，在並行的多個處理器的每一個的所述運算時間結束時，處理結束。從而，可以有效進行通信處理和運算處理，縮短到處理結束為止的時間。
第3發明的特徵為在第1發明的並行處理方法的作業分配方法中，向各處理器交替分配通信時間與運算時間之比大於和小於所述規定值或所述處理器個數的倒數的作業。
另外，第4發明的特徵在於在第2發明的並行處理方法的作業分配方法中，向各處理器交替分配通信時間與運算時間之比大於和小於所述規定值或所述處理器個數的倒數的作業。
根據上述的第3和第4發明，通過交替分配通信時間與運算時間之比大於和小於規定值或處理器個數的倒數的作業的簡單方法，可以有效進行通信處理和運算處理。
另外，第5發明的特徵為在利用由主計算機和通過共用總線與該主計算機連接的多個處理器構成的計算機系統，將由所述主計算機與所述處理器之間的通信處理和所述處理器中的運算處理組成的多個作業通過所述多個處理器進行並行處理的並行處理方法中，用從N(N是整數)到M(大於N的整數)的連續整數對所述多個作業進行編號，如果就要分配完的作業的編號J小於或等於(N+M)/2，則將編號為N+(M-J-1)的作業作為下一次作業進行分配，如果就要分配完的作業的編號J大於(N+M)/2，則將編號為N+(M-J)的作業作為下一次作業進行分配，或者，如果就要分配完的作業的編號J小於(N+M)/2，則將編號為N+(M-J)的作業作為下一次作業進行分配，如果就要分配完的作業的編號J大於或等於(N+M)/2，則將編號為N+(M-J-1)的作業作為下一次作業進行分配，如上分配各作業，使得所述通信時間和所述運算時間之比的平均值為規定值。
該第5發明中，用從N(N是整數)到M(大於N的整數)的連續整數按照通信時間與運算時間之比從小到大或從大到小的順序對作業編號。從而，多個作業的大小的波動變小。
從而，當處理器中先前處理的作業編號大於全體作業編號中的中間值時，分配作業編號小的作業作為下一次作業，先前處理的作業編號小於全體作業編號中的中間值時，分配作業編號大的作業作為下一次作業。
從而，令作業的通信時間與運算時間之比的平均值大致為處理器個數的倒數，可以有效進行通信處理和運算處理，縮短至處理結束為止的時間。
另外，第6發明的特徵為在利用由主計算機和通過共用總線與該主計算機連接的多個處理器構成的計算機系統，將由所述主計算機與所述處理器之間的通信處理和所述處理器中的運算處理組成的多個作業通過所述多個處理器進行並行處理的並行處理方法中，將所述多個處理器分割成G個(G是大於或等於2的整數)處理器群，群內的所述處理器個數大致相等，同時將所述多個作業分割成G個作業群，群內的所述作業個數大致相等，使所述處理器群和所述作業群一一對應，一個作業群內的作業分配給對應的一個處理器群內的處理器，使由所述通信時間和運算時間組成的大小與所述通信時間和所述運算時間之比近似的作業分別屬於所述各個不同的作業群，同時，將由所述通信時間和運算時間組成的大小與所述通信時間和所述運算時間之比近似的作業分配到所述各個作業群內，其分配順序在所述多個作業群中互不相同。
該第6發明中，將多個處理器分割成G個(G是大於或等於2的整數)處理器群，群內的處理器個數大致相等。另外，將多個作業分割成G個作業群，群內的作業個數與處理器群的個數大致相等。從而，處理器群和作業群一一對應，一個作業群內的作業分配給對應的一個處理器群內的處理器。
該情況下，可將由通信時間和運算時間組成的大小與通信時間和運算時間近似的作業分散，使其分別屬於不同的作業群，而且，可將由通信時間和運算時間組成的大小與通信時間和運算時間近似的作業分散地分配到各個作業群內，使其分配順序在多個作業群中互不相同，可使多個作業的通信處理在共用總線上不會形成擁擠狀態。
從而，可有效進行通信處理和運算處理，縮短到處理結束為止的時間。
另外，第7發明是採用由主計算機和多個處理器構成的計算機系統進行分子軌道計算的並行處理方法，所述分子軌道計算是計算用n個(n是正整數)收縮殼(縮約シエル，contracted shell)表示的分子的能量，其特徵在於它執行以下計算，即，將收縮殼R、S、T、U分別包含的原始殼r、s、t、u的各個分量、即原始基底函數i、j、k、l作為指標而表示的2電子積分函數g的函數值g(i，j，k，l)、將以所述原始基底函數k為一個構成元素的收縮基底函數K和以所述原始基底函數1為一個構成元素的收縮基底函數L作為指標而表示的密度矩陣P的元素P(K，L)與係數A1的積A1·P(K，L)·g(i，j，k，l)的所有收縮基底函數的總和f1(I，J)；和所述2電子積分函數的函數值g(i，k，j，l)、所述密度矩陣P的元素P(K，L)與係數A2的積A2·P(K，L)·g(i，k，j，l)的所有收縮基底函數相關的總和f2(I，J)；之和f(I，J)＝f1(I，J)+f2(I，J)，用以所述原始基底函數i、j為一個構成元素的所述收縮基底函數I、J中包含的所有所述原始基底函數的和進行表示的福克矩陣F的所有矩陣元素F(I，J)的計算；令最外側的循環為與滿足R≤nmax(nmax是賦予n個收縮殼的編號的最大值)和T≤R關係的所述收縮殼R和T的組合相關的循環，令所述最外側的循環的內側的第2循環為與所述收縮殼S相關的循環，比所述第2循環更靠內側的第3循環為與所述收縮殼U相關的循環，或令所述第2循環為與所述收縮殼U相關的循環，所述第3循環為與所述收縮殼S相關的循環，令所述收縮殼S的可取值範圍小於或等於R，令所述收縮殼U的可取值範圍小於或等於R，在所述第3循環的內側執行的規定的2電子積分的計算和利用該結果的規定的福克矩陣元素的一部分的計算；在歸攏所述第2和第3循環而形成一個作業單位、將各個所述作業單位分配到所述處理器中進行處理的並行處理方法中，所述作業通過向所述收縮殼R的軌道量子數高的作業分配小編號、向所述收縮殼R的軌道量子數低的作業分配大編號而形成。
該第7發明的並行處理方法中，採用非經驗分子軌道計算的福克矩陣計算算法進行的福克矩陣的計算不受控於主計算機和處理單元之間的通信性能和主計算機的處理性能，可以高速進行計算。
該場合中，與收縮殼R和T相關的循環由主計算機控制，與R和T的組合的固定的S和U相關的循環部分分配給處理單元。
由於有R≥T、S、U的關係，R的編號大的收縮殼其循環次數也多。另一方面，R的編號小的收縮殼其循環次數也少。另外，軌道量子數高的殼其計算所必要的密度矩陣需要很多，通信量也增大相應的量，軌道量子數低的殼其密度矩陣變少，通信量也減少相應的量。
從而，如該第7發明，如果向收縮殼R的軌道量子數高的作業分配小的作業編號，向收縮殼R的軌道量子數低的作業分配大的作業編號，則可減少由運算處理和通信處理之和組成的作業的大小的波動。
從而，可以容易地向並行處理的多個處理單元進行有效的作業分配。
因而，在該第7發明的分子軌道計算的並行處理方法中，採用前述的第1發明、第2發明、第3發明、第4發明或第6發明的任何一個作業分配方法，通過向所述多個處理器分配所述作業，可以有效進行通信處理和運算處理，縮短處理結束的時間。
附圖簡述
圖1是表示本發明實施例採用的計算機系統的一個例子的方框圖。
圖2是表示本發明實施例採用的計算機系統的其他例的方框圖。
圖3是以程序代碼形式表示本發明實施例的RT並行算法的圖。
圖4是表示本發明實施例的RT並行算法的流程圖。
圖5是說明對本發明實施例採用的數據進行雙緩衝時存儲器區域的使用方法的圖。
圖6是表示本發明實施例中，從主計算機向處理單元發送的密度矩陣信息的格式的一個例子的圖。
圖7是表示本發明實施例的密度矩陣數據塊的構成例的圖。
圖8是表示本發明第1實施例的分子軌道計算中並行處理器數和SCF計算的處理時間的關係的圖。
圖9是表示本發明第1實施例的分子軌道計算中並行處理器數和處理器運轉率的關係的圖。
圖10是表示本發明第1實施例的分子軌道計算中各個並行處理器的處理的結束時間的圖。
圖11是表示效率低的處理方法和效率高的處理方法中通信處理和計算處理的進行狀況的模式圖。
圖12是表示本發明第1實施例的分子軌道計算中每個作業發生的通信量和計算量的相關關係的圖。
圖13是表示本發明第2實施例採用的用以向處理單元分配作業的等待矩陣的示例的圖。
圖14是表示本發明第2實施例中並行處理器數和SCF計算的處理時間的關係的圖。
圖15是表示本發明第2實施例中並行處理器數和處理器運轉率的關係的圖。
圖16是表示本發明第2實施例中各個並行處理器的處理的結束時間的圖。
圖17是說明本發明第3實施例中作業群分割方法和作業分配方法的圖。
圖18是表示本發明第3實施例中用以向處理單元分配作業的等待矩陣的示例的圖。
圖19是表示本發明第3實施例中並行處理器數和SCF計算的處理時間的關係的圖。
圖20是表示本發明第3實施例中並行處理器數和處理器運轉率的關係的圖。
圖21是表示本發明第3實施例中各個並行處理器的處理的結束時間的圖。
圖22是說明本發明第4實施例中作業群分割方法和作業分配方法的圖。
圖23是表示本發明第4實施例中用以向處理單元分配作業的等待矩陣的示例的圖。
圖24是表示本發明第4實施例中並行處理器數和SCF計算的處理時間的關係的圖。
圖25是表示本發明第4實施例中並行處理器數和處理器運轉率的關係的圖。
圖26是表示本發明第4實施例中各個並行處理器的處理的結束時間的圖。
圖27是本發明第5實施例中作業群分割方法和作業分配方法的說明圖。
圖28是表示本發明第5實施例中用以向處理單元分配作業的等待矩陣的示例的圖。圖29是表示本發明第5實施例中並行處理器數和SCF計算的處理時間的關係的圖。
圖30是表示本發明第5實施例中並行處理器數和處理器運轉率的關係的圖。
圖31是表示本發明第5實施例中各個並行處理器的處理的結束時間的圖。
圖32是表示原始基底函數與其角動量、軌道指數、原子核座標的對應例的圖。
圖33～圖39是表示非經驗分子軌道計算法的說明中所採用的公式的圖。
發明的最佳實施例以下，參照圖說明將本發明的並行處理方法及其作業分配方法應用於在非經驗分子軌道計算法中進行福克矩陣的計算算法的場合時的實施例。
在說明本發明的並行處理方法及其作業分配方法的實施例之前，對非經驗分子軌道法、用於它的計算機系統的構成例以及該非經驗分子軌道法中的福克矩陣的新計算算法進行說明。
在非經驗分子軌道計算法中，將表示分子狀態的波函數Ψ用相當於分子中的電子空間軌道的電子軌道函數φμ記述。這裡，μ是表示多個分子軌道中的第μ個軌道的附加字符。如圖33(公式1)所示，分子軌道φμ用原子軌道χI的線性組合近似表示。
這裡，(公式1)中，I是表示多個原子軌道中的第I個軌道的附加字符。另外，原子軌道也稱為基底函數。本說明書以下將原子軌道稱為基底函數。另外，(公式1)出現的CIμ是線性組合係數。(公式1)中I的總和是關於構成作為計算對象的分子的全部基底函數的總和。
為了從量子力學的角度記述分子軌道，分子內的電子狀態必須滿足眾所周知的泡利不相容原理。考慮電子的自旋，採用如圖33的(公式2)的斯雷特矩陣式作為記述2n電子體系的分子狀態Ψ的表達式，以滿足泡利不相容原理。這裡，(公式2)中，α(x)和β(x)分別表示第x個電子的自旋向上和向下的狀態。
對2n電子體系的哈密頓算子H，用1電子部分H1與2電子部分H2之和的形式表示，如圖33的(公式3)到(公式5)所示。
圖33的(公式4)中，右邊的(…)內的第1項為電子p的運動能，第2項為第p個電子與第A個原子核的相互作用。(公式4)中，∑p(本說明書中的∑i表示求出關於i的總和，以下同)是全部電子的總和，∑A是全部原子核的總和，ZA是原子核A的電荷，rpA是電子p與原子核A的距離。
另外，(公式5)表示電子p和電子q之間的相互作用，∑p∑q(＞p)是關於2個電子的組合的總和，rpq是電子p、q間的距離。
如果利用上述的哈密頓算子H和(公式2)的斯雷特矩陣式，則分子能量的期望值ε可表示成如圖34的(公式6)～(公式9)。
(公式6)中，∑μ和∑v是n個(n是正整數)分子軌道的總和。(公式7)稱為「コァ積分(core integration)」，以編號1的電子為代表進行書寫。另外，(公式8)和(公式9)分別稱為「庫侖積分」和「交換積分」，以電子1和電子2為代表進行書寫。另外，(公式6)到(公式9)中，dτ、dτ1、dτ2表示位置座標空間中的體積積分。
用基底函數重寫(公式6)，則如圖35(公式10)～(公式13)所示。(公式13)表示的積分稱為「2電子間排斥積分(反発積分)」或省略稱為「2電子積分」。
(公式10)所示分子能量的期望值ε包含有CIμ未知數，這樣無法獲得數值。CIμ是(公式1)中的線性組合常數，μ是從1到n(分子軌道數)的整數，I是從1到N(N是基底函數的個數，為正整數)的整數。以下，以CIμ為元素的N×n矩陣C稱為係數矩陣。
作為決定係數矩陣，使得期望值ε最小，求出基底狀態的波函數Ψ的方法之一，可利用哈特裡·福克·羅湯的變分法(以下稱為HFR法)。省略其導出過程，作為HFR法的結果而獲得的公式如圖36的(公式14)～(公式18)所示。
FIJ、PKL分別稱為福克矩陣元素和密度矩陣元素。以下的說明中有將它們表示成F(I，J)、P(K，L)的情況。它們令I、I、J、K、L各自具有從1到N的值，分別以N×N矩陣的形態進行表示。
通過求解(公式14)，求出係數矩陣。(公式14)相對於從1到n的所有μ以及從1到N的所有I都存在，因而形成n×N個聯立方程式。
在求解(公式14)而獲得的係數矩陣C的計算中，採用密度矩陣P。如(公式18)所示，密度矩陣P從係數矩陣C計算。從而，具體的計算步驟為，首先，提供適當的係數矩陣C，利用它計算出密度矩陣P，並使用該密度矩陣P用(公式15)計算福克矩陣F，求解(公式14)的聯立方程式，獲得新的係數矩陣C。反覆進行上述的計算直到作為密度矩陣P的起源的C和作為結果獲得的C之間的差足夠小，即變成自洽。該反覆計算稱為自洽計算(以下稱為SCF計算)。
實際的計算中最消耗時間的是(公式15)的福克矩陣元素FIJ的計算。這是因為，必須對所有的I、J計算該(公式15)，以及必須對各I、J的組合計算密度矩陣元素PKL的K、L的和。
SCF計算的方法有兩種。一種叫磁碟存儲SCF法，將第一次SCF計算時獲得的2電子積分的值全部保存到磁碟，第二次開始從磁碟讀取必要的2電子積分。另一種叫直接SCF法，在每次計算SCF時重新進行2電子積分的計算。
現在，由於磁碟容量的限制和訪問時間的長短等，後者即直接SCF法的利用成為主流。在採用該直接SCF法的分子軌道計算中，由於每1次SCF計算必須進行大致與N4成比例的個數的2電子積分的計算，因而2電子積分計算的高速進行與分子軌道計算的高速化有直接的聯繫。
這裡預先說明2電子積分G(I，J，K，L)、密度矩陣P(K，L)和福克矩陣F(I，J)的對稱性。
從(公式13)可以明白，2電子積分具有如圖26的(公式19)所示的對稱性。從而，如果能夠獲得(公式19)內的其中一個數值，則可以獲得其他7個數值。
另外，從圖36的(公式18)可以明白P(K，L)＝P(L，K)，從圖26的(公式15)和圖25的(公式11)可以明白F(I，J)＝F(J，I)。
非經驗分子軌道法中，一般採用如圖37的(公式20)所示的基底函數。該(公式20)中，r、n、R是矢量，帶附加字符x、y、z者表示其分量。r是電子的座標，n是電子的角動量，R是原子核的座標。
nx+ny+nz＝入是角動量的大小，也叫軌道量子數。該軌道量子數入為0時該軌道稱為s軌道，為1時該軌道稱為p軌道，為2時該軌道稱為d軌道。
ζm是軌道指數，表示軌道的空間擴展狀態。有用軌道指數不同的多個軌道的線性組合表示一個基底函數的場合，這樣表示的基底函數稱為收縮基底函數，線性組合係數dm稱為收縮係數，與此相對，線性組合前圖37的(公式21)形式的函數 稱為原始基底函數。按照慣例，收縮基底函數χ附上如I、J、K、L的大寫字符編號，原始基底函數 附上如i、j、k、l的小寫字符編號，本說明書中也依從該慣例。
軌道量子數為1時，收縮基底函數存在三種情況，即，n＝(1，0，0)，n＝(0，1，0)，n＝(0，0，1)。同樣地，軌道量子數為2時存在6種情況(或，根據基底函數的構成方式為5種)的收縮基底函數。
(公式20)中圖37的(公式22)所示部分相同的多個收縮基底函數的集合稱為收縮殼。p軌道的收縮殼由3個收縮基底函數構成，另外，d軌道的收縮殼由6個(或5個)收縮基底函數構成。為了方便，在s軌道的情況也將一個收縮基底函數的集合稱為收縮殼。
(公式21)中exp[-ζ(r-R)2]的部分相同的原始基底函數的集合同樣稱為原始殼。通常向收縮殼賦予大寫字母如R、S、T、U，向原始殼賦予小寫字母如r、s、t、u，本說明書中也依照該慣例。
在實施分子軌道計算時，對每個構成作為計算對象的分子的原子預備軌道量子數不同的多個收縮殼，將這些所有的集合作為基底函數集進行利用。可以用原子核座標R和軌道量子數入的組合(R，λ)表示一個收縮殼。
用收縮基底函數表示的2電子積分G(I，J，K，L)若採用原始基底函數，則可表示成圖37的(公式23)。這裡，g(i，j，k，l)可以表示成圖37的(公式24)。
G(I，J，K，L)稱為用收縮基底函數表示的2電子積分，g(i，j，k，l)稱為用原始基底函數表示的2電子積分，以下的說明中，兩者都有簡稱為2電子積分的場合。g(i，j，k，l)也具有圖37的(公式25)所示的對稱性。
原始基底函數 可以用其角動量n、軌道指數C、原子核座標R的組合惟一地表示。假設第i、j、k、l個原始基底函數具有圖32所示表1的角動量、軌道指數、原子核座標。
為了避免複雜的說明，以下的說明中，分別用角動量a、b、c、d代替原始基底函數的編號i、j、k、l，將2電子積分表示成[ab，cd]。
根據文獻1(S.Obara and A.Saika，JCP，vol.84，no.7，p.3964，1986)對利用上述預備的基底函數集計算2電子積分的有效方法進行說明。
首先，a、b、c、d全部為s軌道，即a＝0a＝(0，0，0)，b＝0b＝(0，0，0)，c＝0c＝(0，0，0)，d＝Od＝(0，0，0)時，如圖38的(公式26)～(公式34)所示求出(公式24)的2電子積分。
這裡，(公式26)中出現的[··，··](m)為輔助積分，m是輔助指標，這將在後面說明。(公式27)的積分範圍為從0到1。
另外，a、b、c、d不全為s軌道時，採用圖39的(公式35)和(公式36)所示遞推公式進行計算。
(公式35)中，附加字符i表示x或y或z分量。另外，1I是僅僅i分量為1、其他為0的矢量。而且，Ni(n)表示角動量n的i分量的值。(公式35)具有這樣的性質，即，左邊的輔助積分中出現的一個角動量在右邊確實減少了1以上的量，另外，左邊的輔助積分的輔助指標在右邊增加了相同的量或僅僅增加了1。
輔助指標m為0時，輔助積分[··，··](m)與2電子積分[··，··]完全一致，可用於輔助2電子積分的計算。無論是包含多大角動量的基底函數的2電子積分，都可以反覆利用(公式35)使角動量減少，直到最後全部角動量變成(0，0，0)的輔助積分。由於角動量為(0，0，0)的輔助積分可以用(公式26)計算，因而如果該數值與適當的係數相乘相加，則可獲得2電子積分的數值。
實際的計算如下。
首先，根據(公式35)，用8個以下的輔助積分表示2電子積分。這裡出現的輔助積分也適用(公式35)。反覆進行該步驟，將全部角動量變成(0，0，0)的輔助積分的步驟作為計算步驟記錄下來。
接著，用(公式26)計算角動量為(0，0，0)的輔助積分，從其出發，按照先前的計算步驟計算輔助積分的數值，最後獲得作為目的的2電子積分的數值。
(公式35)還具有另一個重要的性質，即，2電子積分中出現的4個角動量的組合如果相同，則即使軌道指數和原子核座標的組合不同，也能夠採用完全相同的上述計算步驟。進行計算時，可以對應軌道指數和原子核座標僅僅改變與輔助積分相乘的係數。
如上所述，用必須計算的收縮基底函數表示的2電子積分的數相對於收縮基底函數的數N成為N4。而實際必須獲得的數值是用原始基底函數表示的2電子積分的數，其總數可達到用收縮基底函數表示的2電子積分的數的數倍到數十倍(取決於構成收縮基底函數的原始基底函數的數，即收縮數)。
作為減少該個數的方法，首先可考慮利用(公式19)或(公式25)中記述的對稱性。但是，即使用該方法達到最佳效率，2電子積分的計算量也只能為1/8。
另一個方法是積極排除從計算精度的角度可判斷為不必要的2電子積分的計算的方法。不必要的2電子積分的判斷可如下進行。
如上所述，所有的2電子積分的數值可根據(公式26)所示的所有角動量為(0，0，0)的輔助積分
(m)的數值進行計算。從而，可以用
(m)的數值判斷2電子積分的數值對福克矩陣元素的數值的貢獻是否達到計算誤差的程度。而且，
(m)的數值的大小可以從(公式29)所示函數K(ζ，ζ』，R，R』)的值進行判斷，而且函數K(ζ，ζ』，R，R』)的值可以從圖39的(公式37)的大小進行判斷。
從而，通過用(ζa，A，ζb，B)的數值的組合估計(公式26)的第一個函數K的大小，可以判斷2電子積分[ab，**]的計算是否必要，另外，通過用(ζc，C，ζd，D)的數值的組合估計(公式26)的第二個函數K的大小，可以判斷2電子積分[**，cd]的計算是否必要。
從而，將對不必要的2電子積分的計算進行排除稱為「終止」。上述的例中，僅僅從a和b的信息進行判斷並終止的場合也可稱為用ab進行的終止，僅僅從c和d的信息進行判斷並終止的場合也可稱為用cd進行的終止。從而，僅僅從ab或cd可以判斷是否終止，這是因為圖29的(公式37)的最大值為1、下限值為0。通過進行這樣的終止，必須計算的2電子積分變成大致與N2成比例的個數，可以顯著減少計算量。
如上所述，在N大的場合，利用終止減少計算量的效果明顯大於利用2電子積分的對稱性的效果，通過採用該方法，可以顯著縮短非經驗分子軌道計算中福克矩陣計算所需的處理時間。
圖1表示本實施例方法所適用的並行計算系統的一個例子的全體結構，其在先前說明的文獻1中有說明。即，該系統通過共用總線3將多個處理單元2連接到主計算機1。
另外，圖2表示本實施例方法所適用的並行計算系統的一個例子的全體結構，其在先前說明的文獻2中有說明。圖2示例的該系統通過串行總線13將多個板式計算機12以雛菊鏈的方式連接到主計算機11。採用如IEEE1394串行總線作為總線13。
各板式計算機12具有相互連接的多個處理單元14，同時還具有用以連接總線13和多個處理單元14的網橋15。
但是，在如圖1或圖2所示的文獻1或文獻2的系統中，可連接到各個並行處理單元2或14的存儲器容量有限制。當前，各處理單元2或14最多可以連接數10兆字節(以下稱為Mb)左右容量的存儲器。
另外，採用上述具有較高通用性且廉價的·EEE1394串行總線作為連接主計算機1或11和各處理單元2或14的通信網的場合，其通信性能在目前的最佳性能至多可達到400兆字節/秒(以下稱為Mbps)的程度。
本發明的實施例中，在這樣構成的計算機系統中採用新的福克矩陣生成算法，可以不需要高的通信性能，且與各處理節點即處理單元連接的存儲器即使只有上述的目前的容量也可進行高效計算。
圖3說明以程序代碼形式表示的可進行有效並行計算的福克矩陣生成算法。
為了方便說明，圖3中記述了由與收縮殼R、S、T、U相關的4重循環和與其內部的收縮基底I、J、K、L相關的4重循環構成的算法，實際的算法中，令最外側的循環為與滿足R≤Nmax(Nmax是賦予N個收縮殼的編號的最大值。在賦予從0到N的編號時，Nmax＝N。)和R≥T關係的收縮殼R和T的組合(RT)相關的循環。令第2循環為與收縮殼S相關的循環，第3循環為與收縮殼U相關的循環。在第3循環的內側，進行函數值G(R，S，T，U)的計算和採用其結果的規定的福克矩陣元素F的一部分計算。
另外，也可以令第2循環與U相關，第3循環與S相關。即，雖然圖3中與U相關的循環形成於與S相關的循環的內側，但是也可以使該循環的順序逆轉。
與收縮殼R和收縮殼T的組合相關的循環在主計算機上控制，與收縮殼R和收縮殼T的組合固定的收縮殼S和收縮殼U相關的循環部分的處理分配給處理單元。歸攏R和T固定的第2和第3兩個循環，形成一個作業單位，使各個作業單位在多個處理單元2或14中進行處理。
這樣，由於向多個處理單元進行的作業分配以RT對單位進行，因而以下的說明中將該算法稱為RT並行算法。
此時，主計算機1或11執行所有的矩陣元素P的初始值的計算、與處理單元共同進行的SCF計算以及決定是否繼續該SCF計算等。在SCF計算時，主計算機1或11執行向多個處理單元2或14分配R和T固定的作業單位的決定、應該向處理單元發送的矩陣P的一部分的矩陣元素的選擇、向處理單元發送選擇的矩陣元素、從處理單元發送來的矩陣F的一部分的矩陣元素的接收以及採用矩陣F進行的矩陣P的更新。
另一方面，處理單元2或14執行從主計算機1或11發送的矩陣P的一部分的矩陣元素的接收、與收縮殼S相關的循環的控制和與收縮殼U相關的循環的控制、函數G(R，S，T，U)或函數g(i，j，k，l)的計算、矩陣F的一部分的矩陣元素的計算以及向主計算機1或11發送矩陣F的一部分的矩陣元素。
收縮殼R取從0到Nshell-1的值、收縮殼S、T、U取從0到R的值。令I為屬於R的所有收縮基底編號，J為屬於S的所有收縮基底編號，K為屬於T的所有收縮基底編號，L為屬於U的所有收縮基底編號。
另外，圖3中，假定收縮基底被賦予編號，使屬於相同收縮殼的編號連續，令I、J、K、L的範圍分別為從b_basis(R)到e_basis(R)、從b_basis(S)到e_basis(S)、從b_basis(T)到e_basis(T)、從b_basis(U)到e_basis(U)。
這裡，b_basis(X)、e_basis(X)是屬於收縮殼X的收縮基底的編號的最小值和最大值。在與收縮基底相關的4重循環的內部執行2電子積分G(·，J，K，L)的計算和福克矩陣元素的計算。這裡採用的密度矩陣元素是以下4個P(K，L)、P(·，J)、P(K，J)、P(I，L)，另外，計算的福克矩陣元素是以下4個F(·，J)、F(K，L)、F(I，L)、F(K，J)。
這裡，由於I和K是分別形成收縮殼R和T的收縮基底，因而在作業分配時，它們固定成數個(收縮殼是s軌道時為1個，是p軌道時為3個，是d軌道時為6個)。J和L則任意。
圖3中，為了簡潔地記述代碼，S和U取從0到R的R+1個的所有值進行書寫，但實際上S和U並不是取該範圍中的所有值。
屬於R的所有收縮基底和屬於S的所有收縮基底之間，用ab進行終止成立的場合下，由於可以省略所有的G(I，J，*，*)的計算，因而S不必取上述值。另外，與此同時，由於不利用P(I，J)、P(K，J)，不計算F(I，J)、F(K，J)，因而它們不必在主計算機和處理單元之間進行通信。
同樣，屬於T的所有收縮基底和屬於U的所有收縮基底之間，用cd進行終止成立的場合下，由於可以省略所有的G(*，*，K，L)的計算，因而U不必取上述值。另外，與此同時，由於不利用P(I，L)，P(K，L)，不計算F(I，L)，F(K，L)，因而它們不必在主計算機和處理單元之間進行通信。
從而，不僅可以削減與S和U相關的循環次數、削減計算量，而且可以削減不必要的矩陣元素的通信、削減通信量。
用圖4所示流程圖說明採用RT並行算法的處理的流程。以下的說明中採用圖2的系統。另外，圖4中，由於主計算機11和處理單元14執行不同的處理，因而記述了不同的流程圖。
另外，雖然以多個(典型為100個)處理單元14並行連接到主計算機11作為前提，但是由於它們根據同樣的流程進行動作且它們之間的數據不相關，因而只表示了作為代表的一個處理單元14中的處理流程。另外，圖4中虛線表示的箭頭部分表示其後的處理不由其前面的處理支配，而是等待其他處理系統的信息輸入。
首先，說明主計算機11的處理步驟。
主計算機11執行係數矩陣的初始設定(步驟S101)後，進入SCF循環。SCF持續循環直到新計算的係數矩陣變成自洽。
即，在SCF循環內，首先，根據(公式18)從係數矩陣計算密度矩陣(步驟S102)。然後，進入RT循環，首先確定分配給處理單元的RT對編號，即惟一表示兩個收縮殼R和T的組合的編號(步驟S103)。該例的場合中，RT對編號由圖39的(公式38)所示計算式確定。
根據圖3的記述，RT對編號按照編號從小到大的順序進行分配，但是也不必一定按照上述順序，只要能對所有R、T的組合進行處理，則可以通過賦予編號或處理順序，以任何順序進行處理。
接著，將與上述的RT對編號對應的作業中必要的密度矩陣信息向被分配了該RT對編號的處理單元發送(步驟104)，此時，考慮用ab和cd進行的終止，所有在處理單元的計算中不用的密度矩陣數據都不進行發送。
處理單元14接收來自該主計算機11的密度矩陣信息並存儲到接收緩衝存儲器(步驟S201)。然後，對於分配的(RT對)作業，控制與收縮殼S、U相關的循環，進行福克矩陣元素的計算(步驟S202)，然後，計算結束後，將求出的福克矩陣信息存儲到發送緩衝存儲器，從該發送緩衝存儲器向主計算機11發送該求出的福克矩陣信息(步驟S203)。
如上所述，某處理單元14中的處理結束後，主計算機11如果從該處理單元14接收了福克矩陣信息(步驟S105)，則判斷對所有的處理單元進行的RT對編號的分配和密度矩陣信息的發送是否結束(步驟S106)，若未結束，則返回步驟S103，確定新的RT對編號的分配，將對應於該RT對編號的密度矩陣信息向該處理單元14發送。
反覆進行同樣的操作，主計算機11對所有的處理單元進行RT對編號的分配和密度矩陣信息的發送，等待從處理單元接收福克矩陣。
步驟S106中，若判斷所有的RT對編號的處理結束，則主計算機11根據收集的福克矩陣信息求解圖26的(公式14)，計算新係數矩陣(步驟S107)，然後，將新係數矩陣和其之前的係數矩陣比較，判斷是否獲得自洽的解(步驟S108)，若兩者十分一致，則判斷獲得自洽的解，結束計算。如果不一致，則從步驟S108返回步驟S102，根據(公式18)生成新的密度矩陣，重複同樣的操作。
另外，為了儘可能用計算處理隱蔽通信處理，頻繁使用的數據的雙緩衝也可適用於RT並行算法中。
如圖5所示，在各處理單元具有的存儲器中，將用於存儲密度矩陣信息和福克矩陣信息的區域預先分割成A和B兩塊。
然後，決定分別將用密度矩陣信息存儲區域A存儲的密度矩陣元素計算(以下，將該計算稱為類型A的計算)的福克矩陣元素存儲到福克矩陣信息存儲區域A，用密度矩陣信息存儲區域B存儲的密度矩陣元素計算(以下，將該計算稱為類型B的計算)的福克矩陣元素存儲到福克矩陣信息存儲區域B。
使對應於一個RT對編號的作業與類型A或類型B的計算的任何一個相對應，類型A的計算作業結束後開始類型B的計算，類型B的計算作業結束後開始類型A的計算。
在類型A的計算時，將剛剛進行的類型B的計算作業的計算結果保持在福克矩陣信息存儲區域B中，另外，密度矩陣信息存儲區域B成為可自由改寫的區域。
從而，在類型A的計算作業執行過程中，可將剛剛獲得的計算結果從福克矩陣信息存儲區域B讀出並向主計算機發送，另外，可從主計算機接收下一個類型B的計算作業中使用的信息並寫入密度矩陣信息存儲區域B。類型B的計算作業的執行過程中也可以利用區域A進行同樣的數據收發動作。
通過採用這樣的雙緩衝機構，如果可以在計算作業的處理中完成數據收發處理，則可以用計算處理隱蔽通信處理，進行有效的處理。以下所示的計算例中都進行該雙緩衝。
下面用圖6和圖7說明密度矩陣信息的構成。
圖6表示從主計算機11向處理單元14發送的密度矩陣信息的格式的一例。從收縮殼R的編號到收縮殼W[Nw-1]的編號為止為整數型數據，從與收縮殼V
相關的密度矩陣數據塊到與收縮殼W[Nw-1]相關的密度矩陣數據塊為由一個或多個浮點型數據或定點型數據構成的塊。
通過圖6中從上向下的兩個收縮殼R和收縮殼T的編號，確定接收了密度矩陣信息的處理單元14應處理的RT對編號。
收縮殼R和T的編號之後是表示收縮殼的集合V和收縮殼的集合W的元素數的兩個整數型數據Nv和Nw。收縮殼V是其包含的收縮基底和收縮殼R包含的收縮基底的組合中，至少一個用ab進行的終止後剩餘的編號，即用收縮殼S的循環可獲得S的收縮殼編號。
同樣，收縮殼W是其包含的收縮基底和收縮殼R包含的收縮基底的組合中，至少一個用cd進行的終止後剩餘的編號，即用收縮殼U的循環可獲得U的收縮殼編號。
圖7表示密度矩陣數據塊的結構例。該結構例是作為代表例表示的與收縮殼V
相關的密度矩陣數據塊。
收縮殼的軌道量子數大於1時，與該收縮殼相關的密度矩陣數據塊還由與收縮基底相關的子塊構成。圖7所示例是構成收縮殼V
的收縮基底為m+1個即M0(V
)，M1(V
)，…，Mm(V
)的情況，與各個收縮基底相對應的子塊為m+1個。
一個子塊還分成兩個區域。一個是將從構成收縮殼R的收縮基底I0(R)到Ii(R)和M0(V
)作為指標的密度矩陣元素的區域。另一個是將從構成收縮殼T的收縮基底K0(T)到Kk(T)和M0(V
)作為指標的密度矩陣元素的區域。這裡，i+1、k+1分別是構成收縮殼R、T的收縮基底的個數，它們取決於收縮殼R、T的軌道量子數。這些區域包含的密度矩陣元素的個數由收縮殼R和T的軌道量子數確定，從而，一組密度矩陣信息中，任何子塊都為相同的大小。
另外，雖然省略了說明，福克矩陣信息的結構也相同，且其數據量與密度矩陣信息相同。
[關於各作業的形成方法和編號附加]從上述的說明可以明白，可分配到處理單元的作業不僅是計算處理，且包含與主計算機的通信處理。
該實施例中，形成各作業，使得計算處理和通信處理之和組成的作業的大小(size)的波動變小，儘可能使作業的大小變得均等。另外，由於各處理單元具有的存儲器的容量有限制，因而形成各作業，使得該存儲器保持的密度矩陣和福克矩陣的元素數儘可能少。從而，該實施例形成如下的形態。
如上所述，該實施例中，作業以RT對單位向處理單元分配。如果RT對確定，則收縮殼S和U的循環次數也確定。即，R大的場合，S和U的循環次數變多，R小的場合，S和U的循環次數變少。這裡，向R大的作業分配軌道量子數高的殼，向R小的作業分配軌道量子數低的殼。
從而，在RT對的R大的作業的場合，S和U的循環次數雖然變多，但是由於向該作業分配的收縮殼的軌道量子數低，因而與其內部的收縮基底相關的循環次數變多。相反，在R小的作業的場合，雖然S和U的循環次數變少，但是由於收縮殼的軌道量子數高，因而與其內部的收縮基底相關的循環次數變多。從而，取決於由RT對決定的作業的計算量的波動變小。
另外，在RT對的R的編號大的作業的場合，雖然圖6的Nv、Nw變大，但是由於分配給該作業的收縮殼的軌道量子數低，因而密度矩陣信息的數據量不會變得過多，結果，取決於作業的通信量的波動變小。
從而，可以減少作業的大小的波動。
另外，在RT對的R的編號大的場合，由於Nv、Nw變大，因而有必要減少子塊的數據量，以抑制全體的容量。如前所述，子塊的數據量取決於軌道量子數，與軌道量子數低的收縮殼相關的子塊其數據量變少。
該實施例中，RT對的R的編號大的收縮殼的軌道量子數被降低。相反，在RT對的R的編號小的場合，由於Nv、Nw小，因而不必減少子塊的數據量，編號小的收縮殼的軌道量子數被升高。
從而，通過這樣將軌道量子數高的殼分配給編號小的收縮殼，將軌道量子數低的殼分配給編號大的收縮殼，即使在容量小的存儲器中也可以適用於大規模的分子軌道計算。
該實施例中，由於作業以RT對單位分配給處理單元，因而作業編號與RT對編號一致。如前述，RT對編號雖然可以任意決定，但是，例如如果由圖39的(公式38)決定，則可按照R、T的大小以從小到大的順序賦予作業編號。
該例中採用圖2所示計算機系統。該例中，以3殘基肽Glycine-Alanine-Glutamine(以下，記為GAQ。分子式C10H18N4O5)為計算對象，用6-311++G(3d，2p)作為基底函數。
該例中，收縮殼的個數Nshell為336，其中，軌道量子數為0的s軌道的殼為167，軌道量子數為1的p軌道的殼為112，軌道量子數為2的d軌道的殼為57。
該例中，將收縮殼編號0到56分配給d軌道的殼，將57到168分配給p軌道的殼，將169到335分配給s軌道的殼。
而且，該例中，RT對的編號，即，作業編號由圖39的(公式38)決定，按照RT對編號從小到大的順序向處理單元進行作業分配。
根據該例，用RT並行算法僅僅執行1次SCF循環時所需處理時間和處理單元數的關係的一個例子形成如圖8所示的情況。
圖8中，虛線所示直線表示處理時間與處理單元數成反比例減少的理想情況。該第1例中，可判斷當處理單元數增加到100附近時，離開理想直線，變成了不是可伸縮的並行處理。
另外，圖9表示該第1例中，全體處理時間中處理單元進行處理的時間所佔的比例(運轉率)，處理器數從100附近開始，運轉率下降。
該原因可認為是，相對於隨著處理單元數的增加，系統全體的計算處理能力提高，主計算機和處理單元之間的通信性能維持一定的情況下通信量增大，從而通信時間超過計算時間，處理單元等待數據接收而不進行計算的時間增大。
成為不是可伸縮的又一個原因可認為是向並行處理器分配計算負荷不均一。但是，從圖10所示的全部處理單元中處理結束時間的分布，可以明白計算負荷的分配大致均一。
並行處理單元中計算時間的合計為36389秒，若將其平均分配給100個處理器則變成363.89秒的計算處理。相對地，通信時間的合計為363.02秒，與計算時間大致相等。
但是，如圖10所示，第1例的並行處理中各處理單元的計算時間變成420秒左右。因而，可以說第1例的並行處理的效率差。
圖11是表示通信處理和單一處理單元中計算處理的進行狀況在處理效率低和處理效率高的情況下的比較模式圖。圖11中，網點部分為正在進行處理的時間帶。該網點部分的合計長度在通信時和計算時相同，另外，在效率低的場合和高的場合也相同。
在效率低的處理的場合中，如圖中的空白部分所示，產生既不進行通信也不進行計算處理的時間帶。從而，全體的到處理結束的時間變長。相對地，如果進行效率高的處理，則通信處理和計算處理都不停止，處理結束的時間變短。
圖12表示上述的第1例中每個作業發生的計算時間和通信時間的關係。該圖12是按作業編號從全部56616個作業中等間隔地抽出100個作業而繪製的。如圖12中的參照指標所示，對應作業中的收縮殼R和T的軌道量子數的組合，繪製的形狀發生變化。例如，收縮殼R的軌道量子數為1即p軌道、收縮殼T的軌道量子數為2即d軌道的場合的組合(pd)繪製成黑正方形的點。
從該圖12可以判斷，作業的大小的波動即使小，通信時間和計算時間的比例(比)也因作業而異。圖12中的點劃線是通信時間和計算時間之比為0.01的線。處理單元數為100時，如果通信時間和計算時間之比在該線以下的作業很多，則通信量變大，在計算處理中產生等待。相反，如果通信時間和計算時間之比在該線以上的作業很多，則計算量變大，變得容易隱蔽通信處理。
如上所述，在全體的通信時間和計算時間大致相等的場合，則無論在任何時刻，若控制作業的分配，使與在該時刻並行處理的作業相關的通信量和計算量之比的平均值落在點劃線上，則可以進行效率高的並行處理。
另外，該例中，收縮殼編號的確定方法如上所述，以軌道量子數高的殼取小編號、軌道量子數低的殼取大編號進行分配，在R大的場合，由於不會使密度矩陣信息的數據量變得過多，因而取決於作業編號的通信量的波動變小。另外，如上所述，採用上述收縮殼編號的確定方法時，取決於作業編號的計算量的波動也變小。
如果收縮殼編號不是以軌道量子數高的殼取小編號、軌道量子數低的殼取大編號進行分配，則計算時間和通信時間的取決於作業編號的波動變得比圖12所示更大，向多個處理單元均等地分配負荷變得更加困難。
考察圖12所示每個作業的計算時間和通信時間的關係，可以明白收縮殼R、T都是s軌道的場合全部位於點劃線以上的區域，而收縮殼R為s軌道、收縮殼T為p軌道的場合的一部分在點劃線以上的區域。
通過進一步考察可以明白，由圖39的(公式38)決定的作業編號如果大於約35000，則繪製曲線在點劃線以上，如果作業編號小於約35000，則繪製曲線在點劃線以下。即，RT對編號小的作業其通信時間與計算時間之比大，RT對編號大的作業其通信時間與計算時間之比小。
以下說明的第2實施例到第5實施例也象上述實施例一樣形成，使得計算時間和通信時間的波動變小，同時，利用由圖39的(公式38)決定的作業編號的作業中具有的如上述圖12所示的性質，進行更有效的作業分配。
根據上述的考察，通過使編號小的作業和編號大的作業混合來進行分配，可以期望實現通信負荷在時間上的分散。該第2實施例中，生成圖13所示的分配等待矩陣，向並行處理單元2或14進行分配。
為了簡單說明，圖13所示例中表示了全部作業數N為33的場合的分配等待矩陣。圖13中，括號外的數字為作業編號，它相當於分子軌道計算中的RT並行算法中的RT對編號。另外，括號內的數字表示進行作業分配的順序。
主計算機參照該等待矩陣，以該等待矩陣的從上到下的順序將作業編號讀出，同時向處理單元分配作業。
這裡，令最初的作業為編號0的作業，以後，若令前面的編號為J，·若J在N/2以下，則將編號為N-J-1的作業·若J在N/2以上，則將編號為N-J的作業作為下一次向處理單元分配的作業。
從而，RT對編號小、通信時間與計算時間之比大的作業和RT對編號大、通信時間與計算時間之比小的作業交互進行分配。從而，與多個處理單元並行處理的作業相關的通信量與計算量之比的平均值為處理單元個數的倒數，處理單元數為100時大約為0.01，可以進行有效的並行處理。
圖14表示採用第2實施例的作業分配方法的並行處理方法的計算中，處理時間和處理單元數的關係。作為該例的計算對象的分子和採用的基底函數，與共同表示圖8結果的第1實施例中的計算對象和基底函數相同，分別為GAQ和6-311++G(3d，2p)。
與圖8的結果相比較，處理單元數為100附近的計算時間約縮短了9％，可實現比前述的第1實施例更高速的處理。
圖15表示該第2實施例的場合中的處理單元的運轉率和處理單元數的關係，與第1實施例的說明中的圖9對應。
從兩者的比較可以判斷，第2實施例的場合中，與第1實施例的例子相比較，在處理單元數為100附近的運轉率變高。
另外，該第2實施例中，處理單元數為100時，各處理單元的處理結束時間如圖16所示。這與第1實施例的圖10對應。可判斷為能向並行處理單元均等地分配負荷，結束時間的波動變小。
另外，令分配等待矩陣的最前面的作業為RT對編號最大的作業，以後，若令前面的編號為J，·若J在N/2以下，則將編號為N-J的作業·若J在N/2以上，則將編號為N-J-1的作業作為下一個向處理單元分配的作業。在該場合也可以獲得與上述同樣的效果。
另外，令任意編號的作業為最前面的作業，以後，若令前面的編號為J，·若J在N/2以下，則將編號為N-J-1的作業·若J在N/2以上，則將編號為N-J的作業作為下一個分配的作業，若其編號小於0或大於最大的RT對編號，則從最大的RT對編號的一半的編號的作業重新開始，以同樣的步驟確定下一次的作業編號，或者採用其他類似的方法，生成分配等待矩陣，也可獲得同樣的效果。
另外，第2實施例中，決定下一次分配的作業的編號時的條件中用於記述的除法是求出的商保留到小數點以下的準確的除法，與第3實施例以後所採用的整除不同。
第3實施例中，將多個處理單元分成群的同時，與之對應，將多個作業也分成相同數量的群，對各群分別準備分配等待矩陣。
即，將多個處理單元分割成G個(G是2以上的整數)處理器群，群內的處理單元數大致相等，同時，將多個作業分割成與處理器群數相同的G個作業群，群內的作業數大致相等。
然後，使處理器群和作業群一一對應，一個作業群內的作業分配給對應的一個處理器群內的處理單元。
該分配方法中，首先，將通信時間與運算時間組成的作業大小和通信時間與運算時間之比彼此近似的作業分別分配給不同的作業群。而且，作業大小和通信時間與運算時間之比近似的作業以在各個處理器群中的分配順序不重疊的狀態分配到各個作業群內，即其在多個作業群中的分配順序互不相同。
在群數G為4、作業數N為33的簡單的場合，用圖17和圖18對該第3實施例的場合的多個作業群中一一對應的多個等待矩陣的生成方法的具體例進行說明。
與前述例相同，圖17、圖18中，括號外的編號表示作業編號即RT對編號，括號內的編號表示在分配到相同等待矩陣的作業群內進行分配的順序。
首先，如圖17所示，向與作業編號J除以作業群數(等待矩陣數)G時的餘數相當的編號g的群分配各作業。這裡，在各等待矩陣內，該分配的作業暫時按照編號順序排列。
接著，用作業編號J除以群數G(使用捨去小數點以下位的整除，以下同)時的商進行分塊。圖17的例中，各塊編號b為該商。
這裡，隸屬各塊編號b的多個作業的作業編號接近，如圖12所示，作業大小且計算時間與計算時間之比變得近似，這些作業分配給各不相同的等待矩陣。
全部作業數N除以群數G的商為B時，全部作業數N為群數G的倍數的場合下，塊數變成B，而在非上述的場合下，塊數變成B+1。後者的場合中，存在有最後的塊有作業編號的等待矩陣和最後的塊無作業編號的等待矩陣。
接著，第g個作業群(第g個等待矩陣)內的作業中，令B除以群數G的商為x，將大於或等於x×g而小於x×(g+1)的編號的作業塊中包含的作業作為最初的作業。這是因為相同塊內的作業在多個作業群中的順序不同。
圖14的例中，因為B＝N/G＝33/4＝8，x＝B/G＝8/4＝2，如果是第0等待矩陣的作業群，則從大於或等於x×g＝2×0＝0而小於x×(g+1)＝2×1＝2的編號0或1的塊中選擇開始作業。該例中，選擇適合上述條件的最小的編號作為開始作業。
以下所示計算例中也採用該方式，但也可以從適合條件的編號中任意選擇開始編號。
接著，各作業群中，就要分配完的作業包含在第b個作業塊的場合時，以第b+1個作業塊內的作業作為下一次的作業編號。但是，如果第b+1個作業塊內沒有第g個群內的作業，則以第0個作業塊內的作業作為下一次作業。
圖14的例中，第1等待矩陣的作業群中，b＝6的第6個塊包含的編號25的作業的下一次作業變成b+1＝7的第7個塊包含的編號29的作業，其下一次作業變成第0個塊內的編號1的作業(由於沒有第8個塊包含的第1個群的作業)。
另外，該例中，下一次作業為第b+1個作業塊內的作業，但是下一次作業也可以為第b-1個作業塊內的作業。該場合中，b-1如果為負，則包含有第g個群的作業的最大編號的作業塊內的作業作為下一次作業。
圖18表示如上所述確定順序、根據各作業群內的分配順序重排作業編號後各作業群的等待矩陣。
圖19表示第3實施例的計算中處理時間和處理單元數的關係。
作為計算對象的分子、採用的基底函數與第1實施例相同。另外，令各處理單元的運算處理能力彼此相同，5個處理單元構成一個處理器群。
從該圖19可以判斷，根據該第3實施例，與圖8的結果比較，處理單元數為100附近的計算時間約縮短了12％，可實現比第2實施例更高速的處理。
圖20表示該第3實施例的場合的計算例中處理單元的運轉率和處理單元數的關係，與第1實施例說明中的圖9對應。根據該圖，與第1實施例比較，在處理單元數為100附近時運轉率變高，接近100％。
另外，圖21表示該第3實施例中，處理單元數為100的場合的各處理單元的處理結束時間。雖然結束時間的波動為4秒左右，但是可大致均等地向並行處理單元分配負荷。
第4實施例在將處理單元分成群、對各群準備分配等待矩陣的方面與第3實施例相同，但是處理單元的分群方法與第3實施例不同。
在群數G為4、作業數N為33的簡單的場合，用圖22和圖23對該第4實施例的場合的多個作業群分別對應的等待矩陣的生成方法進行說明。另外，圖22、圖23中，括號外的編號表示作業編號即RT對編號，括號內的編號表示在分配到相同等待矩陣的作業群中進行分配的順序，與前述實施例相同。
首先，如圖22所示，分配各作業，使得作業編號J除以作業群數(等待矩陣數)G的2倍即2×G時的餘數等於g或2×G-g-1的作業包含在編號g的群中。在各等待矩陣內，分配的作業暫時按照編號順序排列。
接著，用作業編號J除以群數G(使用捨去小數點以下位的整除，以下同)時的商進行分塊。圖22中，各塊編號b為該商。
全部作業數N除以群數G的商為B時，全部作業數N為群數G的倍數的場合下，塊數變成B，而在非上述的場合下，塊數變成B+1。後者的場合中，存在有最後的塊有作業編號的等待矩陣和最後的塊無作業編號的等待矩陣。
接著，第g個作業群(第g個等待矩陣)內的作業中，令B除以群數G的商為x，將大於或等於x×g而小於x×(g+1)的編號的作業塊中包含的作業作為最初的作業。這是因為相同塊內的作業在多個作業群中的順序不同。
圖22的例中，因為B＝N/G＝33/4＝8，x＝B/G＝8/4＝2，如果是第0等待矩陣的作業群，則從大於或等於x×g＝2×0＝0而小於x×(g+1)＝2×1＝2的編號0或1的塊中選擇開始作業。該例中，選擇適合上述條件的最小的編號作為開始作業。
以下所示計算例中也採用該方式，但也可以從適合條件的編號中任意選擇開始編號。
接著，各作業群中，就要分配完的作業包含在第b個作業塊的場合時，以第b+1個作業塊內的作業作為下一次的作業編號。但是，如果第b+1個作業塊內沒有第g個群內的作業，則以第0個作業塊內的作業作為下一次作業。
圖22的例中，第1等待矩陣的群中，b＝6的第6個塊包含的編號25的作業的下一次作業變成b+1＝7的第7個塊包含的編號30的作業，其下一次作業變成第0個塊內的編號1的作業(由於沒有第8個塊包含的第1個群的作業)。
另外，該例中，下一次作業為第b+1個作業塊內的作業，但是下一次作業也可以為第b-1個作業塊內的作業。該場合中，b-1如果為負，則包含有第g個群的作業的最大編號的作業塊內的作業作為下一次作業。
圖23表示如上所述確定順序、根據各作業群內的分配順序重排作業編號後各作業群的等待矩陣。
圖24表示第4實施例的計算中處理時間和處理單元數的關係。作為計算對象的分子、採用的基底函數與第1實施例相同。另外，令各處理單元的運算處理能力彼此相同，5個處理單元構成一個處理器群。
從圖24可以判斷，根據該第4實施例，與圖8的結果比較，處理單元數為100附近的計算時間約縮短了12％，可實現比第2實施例更高速的處理。
圖25表示該第4實施例的場合的計算例中處理單元的運轉率和處理單元數的關係，與第1實施例說明中的圖9對應。根據該圖，與第1實施例比較，在處理單元數為100附近時運轉率變高，接近100％。
另外，圖26表示該第4實施例中，處理單元數為100的場合的各處理單元的處理結束時間。雖然結束時間的波動為3.5秒左右，但是可大致均等地向並行處理單元分配負荷。
第5實施例在將處理單元和作業分成一一對應的群、對各群準備分配等待矩陣的方面與第3和第4實施例相同，另外，處理單元的分群方法與第3實施例相同，但是群內的分配順序的確定方法與第3和第4實施例不同。
在群數G為4、作業數N為65、各群的處理單元數為2的簡單的場合，用圖27和圖28對該第5實施例的場合的多個作業群分別對應的等待矩陣的生成方法進行說明。另外，圖27、圖28中，括號外的編號表示作業編號即RT對編號，括號內的編號表示在分配到相同等待矩陣的作業群中進行分配的順序，與前述實施例相同。
首先，如圖27所示，分配各作業，使得作業編號J除以作業群數(等待矩陣數)G時的餘數等於g的作業包含在編號g的群中。該分配方法與第3實施例相同，但也可以用與第4實施例相同的方法進行分配。在各等待矩陣內，分配的作業暫時按照編號順序排列。
接著，用作業編號J除以群數G(使用捨去小數點以下位的整除，以下同)時的商進行分塊。圖22中，各塊編號b為該商。
全部作業數N除以群數G的商為B時，全部作業數N為群數G的倍數的場合下，塊數變成B，而在非上述的場合下，塊數變成B+1。後者的場合中，存在有最後的塊有作業編號的等待矩陣和最後的塊無作業編號的等待矩陣。
接著，第g個作業群(第g個等待矩陣)內的作業中，令B除以G的商為x，且令x除以分配到群內的處理單元數m的商為y，將大於或等於y×g而小於y×(g+1)的編號的作業塊中包含的作業作為最初的作業。這是因為相同塊內的作業在多個作業群中的順序不同。
圖27的例中，因為B＝N/G＝65/4＝16，x＝B/G＝16/4＝4，y＝x/m＝4/2＝2，如果是第0等待矩陣的作業群，則從大於或等於y×g＝2×0＝0而小於y×(g+1)＝2×1＝2的編號0或1的塊中選擇開始作業。該例中，選擇適合上述條件的最小的編號作為開始作業。
以下所示計算例中以選擇適合上述條件的最小編號的方式進行，但也可以從適合條件的編號中任意選擇開始編號。另外，選擇開始作業的塊的條件也可以與第3或第4實施例相同。
接著，各作業群中，就要分配完的作業包含在第b個作業塊的場合時，以第b+B/m個作業塊內的作業作為下一次的作業編號。但是，如果第b+B/m個作業塊內沒有第g個群內的作業，則以編號等於b+1除以(B/m)的餘數的作業塊內的作業作為下一次作業。
圖27的例中，第1等待矩陣的群中，b＝7的第7個塊包含的編號29的作業的下一次作業變成b+(B/m)＝7+(16/2)＝15的第15個塊包含的編號61的作業。令b＝15，b+(B/m)＝15+(16/2)＝23，由於沒有第23個塊包含的第1個群的作業，因而其下一次作業變成與b+1＝16除以(B/m)＝8的餘數相等的第0個塊內的編號1的作業。
另外，該例中，下一次作業為第b+B/m個作業塊內的作業，但是下一次作業也可以為第b-B/m個作業塊內的作業。該場合中，如果b-B/m為負且b＝0，則其編號除以(B/m)後的餘數等於(B/m)-1的作業塊中包含有第g個群的作業的最大編號的作業塊內的作業作為下一次作業，如果b-B/m為負且b不為0，則其編號除以(B/m)後的餘數與b-1除以(B/m)後的餘數相等的作業塊中包含有第g個群的作業的最大編號的作業塊內的作業作為下一次作業。
圖28表示如上所述確定順序、根據各群內的分配順序重排作業編號後的等待矩陣。
圖29表示第5實施例的計算中處理時間和處理單元數的關係。作為計算對象的分子、採用的基底函數與第1實施例相同。另外，令各處理單元的運算處理能力彼此相同，5個處理單元構成一個處理器群。
從圖29可以判斷，根據該第5實施例，與圖8的結果比較，處理單元數為100附近的計算時間約縮短了13％，可實現比第3、第4實施例更高速的處理。
圖30表示該計算例中處理單元的運轉率和處理單元數的關係，與第1實施例說明中的圖9對應。根據該圖，與以前的實施例比較，在處理單元數為100的附近運轉率變高，接近100％。
另外，圖31表示該第5實施例中，處理單元數為100的場合的各處理單元的處理結束時間。可以確認結束時間的波動減少到1.5秒左右，並可以均等地向並行處理單元分配負荷。
雖然以上說明的第3、第4、第5實施例中由具有相同運算處理性能的5個處理單元構成處理器群，但是沒有必要將處理單元的個數限於此。
另外，所有的處理單元的運算處理性能不必相同，例如，可以用兩個具有2倍運算處理性能的處理單元構成一個處理器群，用4個具有1倍運算處理性能的處理單元構成其他處理器群等，使得各群之間，處理器群內的總的運算處理性能相同。
另外，上述實施例中，以用非經驗分子軌道計算中的RT並行算法的情況為例進行了本發明的說明，但是在其他並行處理中也可以應用本發明。
權利要求
1.一種並行處理方法中的作業分配方法，其特徵在於在利用由主計算機和通過共用總線與該主計算機連接的多個處理器構成的計算機系統，將由所述主計算機與所述處理器之間的通信處理和所述處理器中的運算處理組成的多個作業通過所述多個處理器進行並行處理的並行處理方法中，向所述各處理器分配各作業，使所述作業的通信時間與運算時間之比的平均值為規定值。
2.如權利要求1所述的並行處理方法中的作業分配方法，其特徵在於在該方法中，所述多個作業的全體通信時間與向所述多個處理器均等分配所述多個作業時的一個作業內的運算時間的總和大致相等時，向所述各個處理器分配各作業，使得所述作業的通信時間與運算時間之比的平均值為所述處理器個數的倒數。
3.如權利要求1所述的並行處理方法中的作業分配方法，其特徵在於在該方法中，向各處理器交替分配通信時間與運算時間之比大於和小於所述規定值或所述處理器個數的倒數的作業。
4.如權利要求2所述的並行處理方法中的作業分配方法，其特徵在於在該方法中，向各處理器交替分配通信時間與運算時間之比大於和小於所述規定值或所述處理器個數的倒數的作業。
5.一種並行處理方法中的作業分配方法，其特徵在於，在利用由主計算機和通過共用總線與該主計算機連接的多個處理器構成的計算機系統，將由所述主計算機與所述處理器之間的通信處理和所述處理器中的運算處理組成的多個作業通過所述多個處理器進行並行處理的並行處理方法中，用從N(N是整數)到M(大於N的整數)的連續整數對所述多個作業進行編號，如果就要分配完的作業的編號J小於或等於(N+M)/2，則將編號為N+(M-J-1)的作業作為下一次作業進行分配，如果就要分配完的作業的編號J大於(N+M)/2，則將編號為N+(M-J)的作業作為下一次作業進行分配，或者，如果就要分配完的作業的編號J小於(N+M)/2，則將編號為N+(M-J)的作業作為下一次作業進行分配，如果就要分配完的作業的編號J大於或等於(N+M)/2，則將編號為N+(M-J-1)的作業作為下一次作業進行分配，如上分配各作業，使得所述通信時間和所述運算時間之比的平均值為規定值。
6.一種並行處理方法中的作業分配方法，其特徵在於，在利用由主計算機和通過共用總線與該主計算機連接的多個處理器構成的計算機系統，將由所述主計算機與所述處理器之間的通信處理和所述處理器中的運算處理組成的多個作業通過所述多個處理器進行並行處理的並行處理方法中，將所述多個處理器分割成G個(G是大於或等於2的整數)處理器群，群內的所述處理器個數大致相等，同時將所述多個作業分割成G個作業群，群內的所述作業個數大致相等，使所述處理器群和所述作業群一一對應，一個作業群內的作業分配給對應的一個處理器群內的處理器，使由所述通信時間和所述運算時間組成的大小與所述通信時間和所述運算時間之比近似的作業分別屬於所述各個不同的作業群，同時，將由所述通信時間和運算時間組成的大小與所述通信時間和所述運算時間之比近似的作業分配到所述各個作業群內，其分配順序在所述多個作業群中互不相同。
7.如權利要求6所述的並行處理方法中的作業分配方法，其特徵在於在該方法中，用從N(N是整數)到M(大於N的整數)的連續整數對所述多個作業進行編號，第g個作業群由在所述作業的編號被從0開始的編號替換時其編號除以所述G後的餘數等於g的作業構成，分配各作業，使得所述通信時間和所述運算時間之比的平均值為規定值。
8.如權利要求6所述的並行處理方法中的作業分配方法，其特徵在於在該方法中，用從N(N是整數)到M(大於N的整數)的連續整數對所述多個作業進行編號，第g個作業群由在所述作業的編號被從0開始的編號替換時，作業編號除以2×G後的餘數等於g的作業以及作業編號除以2×G後的餘數等於(2×G-g-1)的作業構成，分配各作業，使得所述通信時間和所述運算時間之比的平均值為規定值。
9.如權利要求7所述的並行處理方法中的作業分配方法，其特徵在於在該方法中，在構成第g個作業群的作業中，最初向處理器分配的作業是由作業編號J除以處理器群個數G的商彼此相等的作業構成並在利用該商以大於或等於0、小於或等於B＝(M-N+1)/G的整數編號的作業塊中，具有大於或等於(B/G)×g、小於(B/G)×(g+1)的編號的作業塊中所包含的編號的作業。
10.如權利要求8所述的並行處理方法中的作業分配方法，其特徵在於在該方法中，在構成第g個作業群的作業中，最初向處理器分配的作業是由作業編號J除以處理器群個數G的商彼此相等的作業構成並在利用該商以大於或等於0、小於或等於B＝(M-N+1)/G的整數編號的作業塊中，具有大於或等於(B/G)×g、小於(B/G)×(g+1)的編號的作業塊中所包含的編號的作業。
11.如權利要求7所述的並行處理方法中的作業分配方法，其特徵在於在該方法中，構成對應處理器群的處理單元數為m的第g個作業群所包含的作業中，最初向處理器分配的作業是由作業編號J除以處理器群個數G的商彼此相等的作業構成並在利用該商以大於或等於0、小於或等於B＝(M-N+1)/G的整數編號的作業塊中，具有大於或等於(B/G/m)×g、小於(B/G/m)×(g+1)的編號的作業塊中所包含的編號的作業。
12.如權利要求8所述的並行處理方法中的作業分配方法，其特徵在於在該方法中，構成對應處理器群的處理單元數為m的第g個作業群所包含的作業中，最初向處理器分配的作業是由作業編號J除以處理器群個數G的商彼此相等的作業構成並在利用該商以大於或等於0、小於或等於B＝(M-N+1)/G的整數編號的作業塊中，具有大於或等於(B/G/m)×g、小於(B/G/m)×(g+1)的編號的作業塊中所包含的編號的作業。
13.如權利要求9所述的並行處理方法中的作業分配方法，其特徵在於在該方法中，當第g個作業群中，就要分配完的作業包含在第b個作業塊中時，若第(b+1)個作業塊中有第g個作業群的作業則將第(b+1)個作業塊內的作業，或者若第(b+1)個作業塊中沒有第g個作業群的作業則將第0個作業塊內的作業，或者，若(b-1)大於或等於0則將第(b-1)個作業塊內的作業，或者若(b-1)不是大於或等於0則將第g個作業塊內的未分配的最大編號的作業，作為所述第g個作業群的下一個作業進行分配。
14.如權利要求10所述的並行處理方法中的作業分配方法，其特徵在於在該方法中，當第g個作業群中，就要分配完的作業包含在第b個作業塊中時，若第(b+1)個作業塊中有第g個作業群的作業則將第(b+1)個作業塊內的作業，若第(b+1)個作業塊中沒有第g個作業群的作業則將第0個作業塊內的作業，或者，若(b-1)大於或等於0則將第(b-1)個作業塊內的作業，若(b-1)不是大於或等於0則將第g個作業塊內的未分配的最大編號的作業，作為所述第g個作業群的下一個作業進行分配。
15.如權利要求11所述的並行處理方法中的作業分配方法，其特徵在於在該方法中，當第g個作業群中，就要分配完的作業包含在第b個作業塊中時，若第b+(B/m)個作業塊中有第g個作業群的作業則將第b+(B/m)個作業塊內的作業，若第b+(B/m)個作業塊中沒有第g個作業群的作業則將編號等於b+1除以(B/m)後的餘數的作業塊內的作業，或者，若b-(B/m)大於或等於0則將第b-(B/m)個作業塊內的作業，若b為0則將其編號除以(B/m)後的餘數等於(B/m)-1的作業塊中、包含第g個作業群的作業的最大編號的作業塊內的作業，若b不為0則將其編號除以(B/m)後的餘數等於(b-1)除以(B/m)後的餘數的作業塊中、包含第g個作業群的作業的最大編號的作業塊內的作業，作為所述第g個作業群的下一個作業進行分配。
16.如權利要求12所述的並行處理方法中的作業分配方法，其特徵在於在該方法中，當第g個作業群中，就要分配完的作業包含在第b個作業塊中時，若第b+(B/m)個作業塊中有第g個作業群的作業則將第b+(B/m)個作業塊內的作業，若第b+(B/m)個作業塊中沒有第g個作業群的作業則將編號等於b+1除以(B/m)後的餘數的作業塊內的作業，或者，若b-(B/m)大於或等於0則將第b-(B/m)個作業塊內的作業，若b為0則將其編號除以(B/m)後的餘數等於(B/m)-1的作業塊中、包含第g個作業群的作業的最大編號的作業塊內的作業，若b不為0則將其編號除以(B/m)後的餘數等於(b-1)除以(B/m)後的餘數的作業塊中、包含第g個作業群的作業的最大編號的作業塊內的作業，作為所述第g個作業群的下一個作業進行分配。
17.一種並行處理方法，它是採用由主計算機和多個處理器構成的計算機系統進行分子軌道計算的方法，所述分子軌道計算是計算用n個(n是正整數)收縮殼表示的分子的能量，該方法的特徵在於它執行以下計算，即，將收縮殼R、S、T、U分別包含的原始殼r、s、t、u的各個分量即原始基底函數i、j、k、l作為指標而表示的2電子積分函數g的函數值g(i，j，k，l)、將以所述原始基底函數k為一個構成元素的收縮基底函數K和以所述原始基底函數l為一個構成元素的收縮基底函數L作為指標而表示的密度矩陣P的元素P(K，L)與係數A1的積A1·P(K，L)·g(i，j，k，l)的所有收縮基底函數的總和f1(I，J)；和所述2電子積分函數的函數值g(i，k，j，l)、所述密度矩陣P的元素P(K，L)與係數A2的積A2·P(K，L)·g(i，k，j，l)的所有收縮基底函數的總和f2(I，J)；之和f(I，J)＝f1(I，J)+f2(I，J)，用以所述原始基底函數i、j為一個構成元素的所述收縮基底函數I、J中包含的所有所述原始基底函數的和進行表示的福克矩陣F的所有矩陣元素F(I，J)的計算，令最外側的循環為與滿足R≤nmax(nmax是賦予n個收縮殼的編號的最大值)和T≤R關係的所述收縮殼R和T的組合相關的循環，令所述最外側的循環的內側的第2循環為與所述收縮殼S相關的循環，比所述第2循環更靠內側的第3循環為與所述收縮殼U相關的循環，或令所述第2循環為與所述收縮殼U相關的循環，所述第3循環為與所述收縮殼S相關的循環，令所述收縮殼S的可取值範圍小於或等於R，令所述收縮殼U的可取值範圍小於或等於R，在所述第3循環的內側執行的規定的2電子積分的計算和利用該結果的規定的福克矩陣元素的一部分的計算，在歸攏所述第2和第3循環而形成一個作業單位、將各個所述作業單位分配到所述處理器中進行處理的並行處理方法中，通過向所述收縮殼R的軌道量子數高的作業分配小編號、向所述收縮殼R的軌道量子數低的作業分配大編號而形成所述作業。
18.如權利要求17所述的並行處理方法，其特徵在於在該方法中，向所述多個處理器分配各作業，使所述作業的通信時間與運算時間之比的平均值為規定值。
19.如權利要求18所述的並行處理方法，其特徵在於在該方法中，當多個所述作業的全體通信時間與向多個所述處理器均等分配所述多個作業時的一個作業內的運算時間的總和大致相等時，向所述各個處理器分配各作業，使得所述作業的通信時間與運算時間之比的平均值為所述處理器個數的倒數。
20.如權利要求18所述的並行處理方法，其特徵在於在該方法中，分別向所述多個處理器交替分配通信時間與運算時間之比大於和小於所述規定值或所述處理器個數的倒數的作業。
21.如權利要求19所述的並行處理方法，其特徵在於在該方法中，分別向所述多個處理器交替分配通信時間與運算時間之比大於和小於所述規定值或所述處理器個數的倒數的作業。
22.如權利要求17所述的並行處理方法，其特徵在於在該方法中，將所述多個處理器分割成G個(G是大於或等於2的整數)處理器群，群內的所述處理器個數大致相等，同時將所述多個作業分割成G個作業群，群內的所述作業個數大致相等，使所述處理器群和所述作業群一一對應，一個作業群內的作業分配給對應的一個處理器群內的處理器，使由所述通信時間和運算時間組成的大小與所述通信時間和所述運算時間之比近似的作業分別屬於所述各個不同的作業群，同時，將由所述通信時間和運算時間組成的大小與所述通信時間和所述運算時間之比近似的作業分配到所述各個作業群內，其分配順序在所述多個作業群中互不相同。
23.如權利要求17所述的並行處理方法，其特徵在於在該方法中，向軌道量子數高的收縮殼分配小收縮殼編號、向所述軌道量子數低的收縮殼分配大收縮殼編號，所述作業的編號由R(R+1)/2+T計算式確定，用從N(N是整數)到M(大於N的整數)的連續整數進行編號，如果就要分配完的作業的編號J小於或等於(N+M)/2，則將編號為N+(M-J-1)的作業作為下一次作業進行分配，如果就要分配完的作業的編號J大於(N+M)/2，則將編號為N+(M-J)的作業作為下一次作業進行分配，或者，如果就要分配完的作業的編號J小於(N+M)/2，則將編號為N+(M-J)的作業作為下一次作業進行分配，如果就要分配完的作業的編號J大於或等於(N+M)/2，則將編號為N+(M-J-1)的作業作為下一次作業進行分配，如上分配各作業，使得所述通信時間和所述運算時間之比的平均值為規定值。
24.如權利要求22所述的並行處理方法，其特徵在於在該方法中，向軌道量子數高的收縮殼分配小收縮殼編號、向軌道量子數低的收縮殼分配大收縮殼編號，所述作業的編號由R(R+1)/2+T計算式確定，用從N(N是整數)到M(大於N的整數)的連續整數進行編號，使第g個作業群由在所述作業的編號被從0開始的編號替換時其編號除以所述G後的餘數等於g的作業構成，分配各作業，使得所述通信時間和所述運算時間之比的平均值為規定值。
25.如權利要求22所述的並行處理方法，其特徵在於在該方法中，向軌道量子數高的收縮殼分配小收縮殼編號、向軌道量子數低的收縮殼分配大收縮殼編號，所述作業的編號由R(R+1)/2+T計算式確定，用從N(N是整數)到M(大於N的整數)的連續整數進行編號，使第g個作業群由在所述作業的編號被從0開始的編號替換時、作業編號除以2×G後的餘數等於g的作業以及作業編號除以2×G後的餘數等於(2×G-g-1)的作業構成，分配各作業，使得所述通信時間和所述運算時間之比的平均值為規定值。
26.如權利要求24所述的並行處理方法，其特徵在於在該方法中，在構成第g個作業群的作業中，最初向處理器分配的作業是由作業編號J除以處理器群個數G的商彼此相等的作業構成並在利用該商以大於或等於0、小於或等於B＝(M-N+1)/G的整數編號的作業塊中，具有大於或等於(B/G)×g、小於(B/G)×(g+1)的編號的作業塊中所包含的編號的作業。
27.如權利要求25所述的並行處理方法，其特徵在於在該方法中，在構成第g個作業群的作業中，最初向處理器分配的作業是由作業編號J除以處理器群個數G的商彼此相等的作業構成並在利用該商以大於或等於0、小於或等於B＝(M-N+1)/G的整數編號的作業塊中，具有大於或等於(B/G)×g、小於(B/G)×(g+1)的編號的作業塊中所包含的編號的作業。
28.如權利要求24所述的並行處理方法，其特徵在於在該方法中，構成對應處理器群的處理單元數為m的第g個作業群所包含的作業中，最初向處理器分配的作業是由作業編號J除以處理器群個數G的商彼此相等的作業構成並在利用該商以大於或等於0、小於或等於B＝(M-N+1)/G的整數編號的作業塊中，具有大於或等於(B/G/m)×g、小於(B/G/m)×(g+1)的編號的作業塊中所包含的編號的作業。
29.如權利要求25所述的並行處理方法，其特徵在於在該方法中，構成對應處理器群的處理單元數為m的第g個作業群所包含的作業中，最初向處理器分配的作業是由作業編號J除以處理器群個數G的商彼此相等的作業構成並在利用該商以大於或等於0、小於或等於B＝(M-N+1)/G的整數編號的作業塊中，具有大於或等於(B/G/m)×g、小於(B/G/m)×(g+1)的編號的作業塊中所包含的編號的作業。
30.如權利要求26所述的並行處理方法，其特徵在於在該方法中，當第g個作業群中，就要分配完的作業包含在第b個作業塊中時，若第(b+1)個作業塊中有第g個作業群的作業則將第(b+1)個作業塊內的作業，或者若第(b+1)個作業塊中沒有第g個作業群的作業則將第0個作業塊內的作業，或者，若(b-1)大於或等於0則將第(b-1)個作業塊內的作業，或者若(b-1)不是大於或等於0則將第g個作業塊內的未分配的最大編號的作業，作為所述第g個作業群的下一個作業進行分配。
31.如權利要求27所述的並行處理方法，其特徵在於在該方法中，當第g個作業群中，就要分配完的作業包含在第b個作業塊中時，若第(b+1)個作業塊中有第g個作業群的作業則將第(b+1)個作業塊內的作業，若第(b+1)個作業塊中沒有第g個作業群的作業則將第0個作業塊內的作業，或者，若(b-1)大於或等於0則將第(b-1)個作業塊內的作業，若(b-1)不是大於或等於0則將第g個作業塊內的未分配的最大編號的作業，作為所述第g個作業群的下一個作業進行分配。
32.如權利要求28所述的並行處理方法，其特徵在於在該方法中，當第g個作業群中，就要分配完的作業包含在第b個作業塊中時，若第b+(B/m)個作業塊中有第g個作業群的作業則將第b+(B/m)個作業塊內的作業，若第b+(B/m)個作業塊中沒有第g個作業群的作業則將編號等於b+1除以(B/m)後的餘數的作業塊內的作業，或者，若b-(B/m)大於或等於0則將第b-(B/m)個作業塊內的作業，若b為0則將其編號除以(B/m)後的餘數等於(B/m)-1的作業塊中、包含第g個作業群的作業的最大編號的作業塊內的作業，若b不為0則將其編號除以(B/m)後的餘數等於(b-1)除以(B/m)後的餘數的作業塊中、包含第g個作業群的作業的最大編號的作業塊內的作業，作為所述第g個作業群的下一個作業進行分配。
33.如權利要求29所述的並行處理方法，其特徵在於在該方法中，當第g個作業群中，就要分配完的作業包含在第b個作業塊中時，若第b+(B/m)個作業塊中有第g個作業群的作業則將第b+(B/m)個作業塊內的作業，若第b+(B/m)個作業塊中沒有第g個作業群的作業則將編號等於b+1除以(B/m)後的餘數的作業塊內的作業，或者，若b-(B/m)大於或等於0則將第b-(B/m)個作業塊內的作業，若b為0則將其編號除以(B/m)後的餘數等於(B/m)-1的作業塊中、包含第g個作業群的作業的最大編號的作業塊內的作業，若b不為0則將其編號除以(B/m)後的餘數等於(b-1)除以(B/m)後的餘數的作業塊中、包含第g個作業群的作業的最大編號的作業塊內的作業，作為所述第g個作業群的下一個作業進行分配。
全文摘要
利用通過共用總線將主計算機和多個處理器連接而構成的並行計算機進行並行處理時可以向各處理器高效分配作業的方法。向各處理器交替分配通信時間與運算時間之比大於和小於規定值或處理器個數的倒數的作業。另外，使由多個處理器和多個作業對應，分割成多個群，使通信時間和運算時間組成的大小與所述通信時間和運算時間之比近似的作業分別屬於各個不同的作業群，而且，將由通信時間和運算時間組成的大小與通信時間和運算時間之比近似的作業分配到各個作業群內，其分配順序在多個作業群中互不相同。
文檔編號G06F9/50GK1439130SQ01811717
公開日2003年8月27日 申請日期2001年4月25日 優先權日2000年4月28日
發明者山田想, 稻畑深二郎, 宮川宣明, 高島一, 北村一泰, 長嶋雲兵 申請人:大正製藥株式會社