JPH03139759A - Processor space allocation method - Google Patents
Processor space allocation methodInfo
- Publication number
- JPH03139759A JPH03139759A JP27905489A JP27905489A JPH03139759A JP H03139759 A JPH03139759 A JP H03139759A JP 27905489 A JP27905489 A JP 27905489A JP 27905489 A JP27905489 A JP 27905489A JP H03139759 A JPH03139759 A JP H03139759A
- Authority
- JP
- Japan
- Prior art keywords
- processor
- real
- processing
- processors
- data
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Multi Processors (AREA)
Abstract
Description
【発明の詳細な説明】
〔概要〕
実プロセッサをデータ平面上に割り当てるプロセッサの
空間割当方式に関し、
実プロセッサを複数に分割した仮想プロセッサ構成につ
いて、データ平面上に操り返し構造でマツピングし、各
実プロセッサの稼動率を向上させて並列処理の効果を高
め、処理時間を短縮することを目的とし、
2次元に配列した実プロセッサをそれぞれ複数に分割し
、この分割した状態で処理対象のデータ平面上に操り返
し構造でマツピングし、データの出発点となるプロセッ
サから平面上を順次伝播する態様で実プロセッサ間通信
路によって通信して処理を行うように構成する。[Detailed Description of the Invention] [Summary] Regarding a processor space allocation method that allocates a real processor on a data plane, a virtual processor configuration in which a real processor is divided into multiple parts is mapped on a data plane in a repetitive structure, and each real processor is In order to improve the utilization rate of the processor, enhance the effect of parallel processing, and shorten the processing time, the real processors arranged in two dimensions are each divided into multiple parts, and in this divided state, the data plane to be processed is The configuration is such that data is mapped in a loop-back structure, and data is communicated and processed through an inter-processor communication path in a manner in which data is sequentially propagated on a plane from a processor that is a starting point.
本発明ば〜実プロセッサをデータ平面上に割り当てるプ
ロセッサの空間割当方式に関するものである。並列計算
機や超並列計算機を用いた高速化において、負荷分散を
均等にし、プロセッサの稼動率を高めることが強く求め
れている。The present invention relates to a processor space allocation method for allocating real processors on a data plane. In increasing speed using parallel computers and massively parallel computers, there is a strong demand for equalizing load distribution and increasing processor utilization.
従来、例えば第2図(イ)に示すように4つの実プロセ
ッサ0O101,10,11を接続し、これを第2図(
ロ)に示すようにデータ平面上に繰り返し構造でマツピ
ングし、菱形の枠で示すように順次伝播する形で実プロ
セッサ間の隣接通信路を用いて通信を行い、第2図(ハ
)に示すようなCADにおける迷路法による経路探索な
どを行うようにしていた。Conventionally, for example, four real processors 0O101, 10, and 11 were connected as shown in FIG.
As shown in Figure 2 (C), mapping is performed in a repetitive structure on the data plane, and communication is performed using adjacent communication paths between real processors in a sequential manner as shown by the diamond-shaped frame, and as shown in Figure 2 (C). Route searches were performed using the maze method in CAD.
従来は、第2図(ロ)菱形の枠で示すように順次伝播し
て処理する際に、第2図(ニ)に示すように、
1回目;実プロセッサ00が1処理単位2回目:実プロ
セッサ01が2処理単位実プロセッサ10が2処理単位
3回目:実ブロセッサOOが4処理単位実プロセッサ1
1が4処理単位
4回目;実プロセッサ01が6処理単位実プロセッサ1
0が6処理単位
5回目:実ブロセッサOOが8処理単位実プロセッサ1
1が8処理単位
処理していた。また、各回の大きい値をとった全体の処
理単位は一下記(1)となる。Conventionally, when processing is sequentially propagated as shown by the diamond-shaped frame in Fig. 2 (b), as shown in Fig. 2 (d), the first time: the real processor 00 is one processing unit, the second time: the real Processor 01 has 2 processing units Real processor 10 has 2 processing units 3rd time: Real processor OO has 4 processing units Real processor 1
1 is 4 processing units 4th time; real processor 01 is 6 processing units real processor 1
0 is 6 processing units 5th time: Real processor OO is 8 processing units Real processor 1
1 was processing 8 processing units. Further, the overall processing unit that takes a large value each time is one or less (1).
全体の処理単位
=1+2+4+6+8=21処理単位・・・(11従っ
て、第2図(ニ)に示すように、データの出発点となる
プロセッサ(例えばプロセッサ00)から見て、奇数距
離に存在するプロセッサと、偶数距離に存在するプロセ
ッサとがそれぞれ高々50%の稼動率しか得られず、並
列計算機システムにおける全体の速度向上効果が実プロ
セッサ数の1/2以下になってしまうという問題があっ
た。Total processing unit = 1 + 2 + 4 + 6 + 8 = 21 processing units... (11 Therefore, as shown in FIG. There is a problem in that the operating rate of the parallel computer system and the processors located at even distances is only 50% at most, and the overall speed improvement effect in the parallel computer system is less than 1/2 of the actual number of processors.
本発明は、実プロセッサを複数に分割した仮想プロセッ
サ構成について、データ平面上に繰り返し構造でマツピ
ングし、各実プロセッサの稼動率を向上させて並列処理
の効果を高め、処理時間を短縮することを目的としてい
る。The present invention maps a virtual processor configuration in which a real processor is divided into a plurality of parts on a data plane in a repetitive structure, improves the utilization rate of each real processor, enhances the effect of parallel processing, and shortens processing time. The purpose is
第1図を参照して課題を解決する手段を説明する。 Means for solving the problem will be explained with reference to FIG.
第1図において、仮想プロセッサ構成1ば、2次元に配
列した実プロセッサをそれぞれ複数に分割して配置した
例である。In FIG. 1, virtual processor configuration 1 is an example in which real processors arranged two-dimensionally are each divided into a plurality of parts and arranged.
プロセッサ割付2は、仮想プロセッサ構成1を処理対象
のデータ平面上に繰り返し構造でマ・ノピングして割り
付けた例である。Processor allocation 2 is an example in which virtual processor configuration 1 is allocated by mapping in a repetitive structure on the data plane to be processed.
本発明は、第1図に示すように、2次元に配列した実プ
ロセッサをそれぞれ複数に分割した仮想プロセッサ構成
1について、処理対象のデータ平面上に繰り返し構造で
マツピングしてブロモ・ノサ割付2を行い、このプロセ
ッサ割付2を行ったうちのデータの出発点となるプロセ
ッサから平面上を順次伝播する態様で実プロセッサ間通
信路3を用いて通信して処理を行うようにしている。As shown in FIG. 1, the present invention creates a Bromo-Nosa allocation 2 by mapping a virtual processor configuration 1 in which real processors arranged in two dimensions are each divided into a plurality of parts onto a data plane to be processed in a repetitive structure. Processing is performed by communicating using the real inter-processor communication path 3 in a manner in which data is sequentially propagated on a plane from the processor that is the starting point of the data subjected to this processor allocation 2.
従って、実プロセッサを複数に分割した仮想プルセッサ
構成1について、データ平面上に繰り返し構造でマツピ
ングし、実プロセッサ間通信路3によって通信して処理
を行うことにより、各実プロセッサの稼動率を向上させ
て並列処理の効果を高め、処理時間を短縮することが可
能となる。Therefore, the utilization rate of each real processor can be improved by mapping the virtual processor configuration 1 in which a real processor is divided into a plurality of parts in a repetitive structure on the data plane and performing processing by communicating through the communication path 3 between real processors. This makes it possible to enhance the effect of parallel processing and shorten processing time.
[実施例〕
次に、第1図を用いて本発明の1実施例の構成および動
作を順次詳細に説明する。[Embodiment] Next, the configuration and operation of an embodiment of the present invention will be sequentially explained in detail using FIG.
第1図(イ)は、実ブロセ・ノサ構成例を示す。FIG. 1(A) shows an example of a real Broce Nosa configuration.
この実プロセッサ構成例は、実ブロセ・ノサ00.01
.10.11の4つを2次元に配列し、配列した隣接す
る実プロセッサ間を実ブロセ・フサ間通信路3を用いて
相互に通信し得るように結んだものである。This real processor configuration example is real Broce Nosa 00.01
.. 10.11 are arranged in two dimensions, and the adjacent real processors arranged are connected using the real processor-fusa communication path 3 so that they can communicate with each other.
第1図(ロ)は、仮想ブロモ・ノサ構成例を示す。FIG. 1(b) shows an example of a virtual Bromo Nosa configuration.
この仮想プロセッサ構成10例は〜第1図(イ)実プロ
セッサ構成例の各実プロセッサを2×2の仮想プロセッ
サに分割して構成したものである。These 10 examples of virtual processor configurations are constructed by dividing each real processor in the example of the real processor configuration in FIG. 1(a) into 2×2 virtual processors.
尚、仮想プロセッサは、2nx2m(n、mは整数)で
あればよく、数が多くなるほど負荷の分散割合が良くな
る。Note that the number of virtual processors may be 2nx2m (n, m are integers), and the larger the number, the better the load distribution ratio.
第1図(ハ)は、プロセッサ割付例を示す。このプロセ
ッサ割付20例は、第1図(ロ)仮想プロセッサ構成例
を、処理対象のデータ平面上に繰り返し構造でマツピン
グして割付けを行ったものである。ここで、データの出
発点となるプロセッサをプロセッサ01としている。こ
のプロセッサ01を中心に菱形の枠の外側に順次伝播し
て処理を行うようにしている。FIG. 1(c) shows an example of processor allocation. These 20 processor allocation examples are obtained by mapping the virtual processor configuration example shown in FIG. 1(b) onto the data plane to be processed in a repetitive structure. Here, the processor that is the starting point for data is referred to as processor 01. Processing is performed by sequentially propagating data to the outside of the diamond-shaped frame around this processor 01.
第1図(ニ)は、処理単位数例を示す。これば、第1図
(ハ)プロセッサ割付例中のデータの出発点となるプロ
セッサ01からデータを順次伝播して処理を行うときの
実プロセッサの処理単位を示す。FIG. 1(d) shows several examples of processing units. This shows the processing unit of the actual processor when processing is performed by sequentially propagating data from processor 01, which is the starting point of data in the processor allocation example of FIG. 1(c).
具体的に説明すると、
1回目:実プロセッサ01が1処理単位2回目:実プロ
セッサOOが1処理単位実プロセッサ01が2処理単位
実プロセンサー1が1処理単位
3回目:実プロセッサ00が3処理単位実プロセッサ0
1が1処理単位
実プロセンサー0が1処理単位
実プロセッサ11が3処理単位
4回目:実プロセッサ00が3処理単位実プロセッサ0
1が2処理単位
実プロセンサー0が4処理単位
実プロセッサ−1が3処理単位
5回目:実プロセッサ00が2処理単位実プロセッサ0
1が6処理単位
実プロセンサー0が6処理単位
実プロセンサー1が2処理単位
となる。これにより、各回において、実プロセッサの遊
びが従来の第2図(ニ)に比較して少なくなり、並列計
算機システムにおける各実プロセッサの稼動率を向上さ
せることができる。具体的に説明すると、第1図(ニ)
において各回の大きい値をとった全体の処理単位は、下
記(2)となる。To explain specifically, 1st time: Real processor 01 performs 1 processing unit. 2nd time: Real processor OO performs 1 processing unit. Real processor 01 performs 2 processing units. Real processor 1 performs 1 processing unit. 3rd time: Real processor 00 performs 3 processes. unit real processor 0
1 is 1 processing unit Real processor 0 is 1 processing unit Real processor 11 is 3 processing units 4th time: Real processor 00 is 3 processing units Real processor 0
1 is 2 processing units Real processor 0 is 4 processing units Real processor - 1 is 3 processing units 5th time: Real processor 00 is 2 processing units Real processor 0
1 is 6 processing units, real processor 0 is 6 processing units, real processor 1 is 2 processing units. As a result, the idle time of the real processors is reduced each time compared to the conventional example shown in FIG. 2(D), and the operating rate of each real processor in the parallel computer system can be improved. To explain specifically, Figure 1 (d)
The overall processing unit that takes a large value each time is as shown in (2) below.
全体の処理単位
=1+2+3+4+6=16処理単位・・・(2)従っ
て、従来の第2回(ニ)の全体の処理単位21に比べて
〜本実流側によれば上記(2)に示すように全体の処理
単位16となり、21/16=1゜31倍だけ高速に処
理することが可能となる。Total processing unit = 1 + 2 + 3 + 4 + 6 = 16 processing units... (2) Therefore, compared to the total processing unit of 21 in the conventional 2nd (d) ~According to the actual flow, as shown in (2) above. The total processing unit becomes 16, and processing can be performed faster by 21/16=1°31 times.
以上説明したように、本発明によれば、実プロセッサを
複数に分割した仮想プロセッサ構成1について、処理対
象のデータ平面上に繰り返し構造でマツピングし、実プ
ロセッサ間通信I!!3によって通信して処理を行う構
成を採用しているため、並列計算機システムにおける各
実プロセッサの稼動率を向上させて並列効果を高め、処
理時間を短縮することができる。また、本発明について
、既存のネットワークのハードウェア変更を行うことな
く、容易に適用することができる。As explained above, according to the present invention, the virtual processor configuration 1 in which the real processor is divided into a plurality of parts is mapped in a repetitive structure on the data plane to be processed, and communication between real processors I! ! Since the configuration is adopted in which processing is performed by communicating through 3, it is possible to improve the operating rate of each real processor in the parallel computer system, enhance the parallel effect, and shorten the processing time. Further, the present invention can be easily applied without changing the hardware of an existing network.
【図面の簡単な説明】
第1図は本発明の1実施例構成図、第2図は従来技術の
説明図を示す。
図中、1は仮想プロセッサ構成、2はプロセッサ割付、
3ば実プロセッサ間通信路を表す。BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 shows the configuration of one embodiment of the present invention, and FIG. 2 shows an explanatory diagram of the prior art. In the figure, 1 is the virtual processor configuration, 2 is the processor allocation,
3 represents the actual inter-processor communication path.
Claims (1)
空間割当方式において、 2次元に配列した実プロセッサをそれぞれ複数に分割し
、この分割した状態で処理対象のデータ平面上に繰り返
し構造でマッピングし、データの出発点となるプロセッ
サから平面上を順次伝播する態様で実プロセッサ間通信
路によって通信して処理を行うように構成したことを特
徴とするプロセッサの空間割当方式。[Claims] In a processor space allocation method that allocates real processors on a data plane, each of the real processors arranged in two dimensions is divided into a plurality of parts, and in this divided state, a repeating structure is created on the data plane to be processed. 1. A processor space allocation method characterized in that processing is performed by communicating through a communication path between real processors in a manner in which data is mapped and sequentially propagated on a plane from a processor serving as a starting point.
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP27905489A JPH03139759A (en) | 1989-10-26 | 1989-10-26 | Processor space allocation method |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP27905489A JPH03139759A (en) | 1989-10-26 | 1989-10-26 | Processor space allocation method |
Publications (1)
Publication Number | Publication Date |
---|---|
JPH03139759A true JPH03139759A (en) | 1991-06-13 |
Family
ID=17605757
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
JP27905489A Pending JPH03139759A (en) | 1989-10-26 | 1989-10-26 | Processor space allocation method |
Country Status (1)
Country | Link |
---|---|
JP (1) | JPH03139759A (en) |
Cited By (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US7356819B1 (en) * | 1999-07-16 | 2008-04-08 | Novell, Inc. | Task distribution |
-
1989
- 1989-10-26 JP JP27905489A patent/JPH03139759A/en active Pending
Cited By (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US7356819B1 (en) * | 1999-07-16 | 2008-04-08 | Novell, Inc. | Task distribution |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
TWI803663B (en) | A computing device and computing method | |
Enslow Jr | Multiprocessor organization—A survey | |
JP2512661B2 (en) | Non-binary hypercube type computer system and network connection method for multiple nodes | |
US20100183028A1 (en) | System And Method For Establishing Sufficient Virtual Channel Performance In A Parallel Computing Network | |
CN107851043A (en) | The dynamically distributes of quick peripheral parts interconnected resources in network group | |
CN111079078A (en) | Parallel solution of lower triangular equations for structured grid sparse matrices | |
CN114386349A (en) | Wiring method and device for system-level digital circuit, equipment and storage medium | |
JPH03139759A (en) | Processor space allocation method | |
JP3653841B2 (en) | Problem area division / allocation method | |
TWI753728B (en) | Architecture and cluster of processing elements and method of convolution operation | |
JPH07114515A (en) | Decentralized memory computer with network for synchronous communication | |
JPH0221028B2 (en) | ||
JPH04362784A (en) | Pattern verification method | |
CN119883557A (en) | Real-time improvement method of embedded Linux platform | |
JPS62115574A (en) | Parallel wiring method | |
Murata et al. | Rolling mapping/mesh: a mapping method/interconnection structure for a mesh with various densities | |
JPH05324584A (en) | Hypercube allocation method | |
KR0157926B1 (en) | Clock period minimizing method | |
JPH0756870A (en) | Data mapping method | |
Davis IV et al. | The performance analysis of partitioned circuit switched multistage interconnection networks | |
KR100520605B1 (en) | Digital signal processor and method using multi segmented buses | |
EP4182793A1 (en) | Communication between host and accelerator over network | |
Seo et al. | Extended flexible processor allocation strategy for mesh-connected systems using shape manipulations | |
JPH0764936A (en) | Parallel computer | |
JPH03102562A (en) | Parallel processing system for design problem |