[go: up one dir, main page]

JPS59146345A - コントロ−ルフロ−並列計算機方式 - Google Patents

コントロ−ルフロ−並列計算機方式

Info

Publication number
JPS59146345A
JPS59146345A JP58020863A JP2086383A JPS59146345A JP S59146345 A JPS59146345 A JP S59146345A JP 58020863 A JP58020863 A JP 58020863A JP 2086383 A JP2086383 A JP 2086383A JP S59146345 A JPS59146345 A JP S59146345A
Authority
JP
Japan
Prior art keywords
node
pointer
register
control tokens
ndr
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
Application number
JP58020863A
Other languages
English (en)
Inventor
Masahiro Sowa
将容 曽和
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Individual
Original Assignee
Individual
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Individual filed Critical Individual
Priority to JP58020863A priority Critical patent/JPS59146345A/ja
Priority to EP84101399A priority patent/EP0118781A3/en
Publication of JPS59146345A publication Critical patent/JPS59146345A/ja
Priority to US07/147,128 priority patent/US4809159A/en
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/44—Arrangements for executing specific programs
    • G06F9/448—Execution paradigms, e.g. implementations of programming paradigms
    • G06F9/4494—Execution paradigms, e.g. implementations of programming paradigms data driven

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Multi Processors (AREA)
  • Advance Control (AREA)

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 本発明は、コントロールトークンと呼ばれる処理権を表
わすトークンの流れにそって処理を実行する並列計算機
方式に関するものである０本方式の大きな特徴は、ノー
ドドライブレジスタ　（ＮＤＲ）と呼ばれるレジスタ、
もしくは、メモリの存在であり、この存在により、従来
、複雑かつ難かしくなりがちであったコントロールフロ
ー並列処理を、簡単なハードウェア構成と簡単な制御で
。
非決定的に、自然な形で行なえるようになった。
このことは、並列処理コンピュータの実用化にとって非
常に重要なことである。ノードドライブレジスタとは、
従来のコンピュータのプログラムカウンタに相当するレ
ジスタで、コントロールトークンとその命令へのポイン
タを格納し、実行可能な命令を指示するために用いられ
る。
コントロールフロー並列計算機のプログラムは。
第１図に示すようなグラフで表現される。このプログラ
ムは、ｌ＝　（ａ−ｔ−ｂ）（ｃ−ｄ）＋ｅを計算する
ためのプログラムで、ｘ＝ａ＋ｂ、ｙ＝ｃ−ｄ、ｚ＝ｘ
ＸＹ、１＝ｚ＋ｅのようにわけて計算を行っている１図
で、Ｎｌ−Ｎ６は、処理単位を表すノードと呼ばれるも
ので、楕円の中に処理内容を書いてその処理を表す、ノ
ードとノードを結ぶ矢印は、アークと呼ばれ、１つのノ
ードに対する矢印の方向によって、入力アーク、出力ア
ークというように区別される。ノード内に書かれた処理
は、そのノー　ドの人力アークのそれぞれに１１つ以上
のコントロールＩ・−クン（図では黒丸で示されている
）が存在するとき開始され、処理の完了と共に、それぞ
れの入力アーク上から、１番そのノードに近いコントロ
ールトークンが１ｔ１ＭｌＩ＆り除かれ、それぞれの出
力アーク上に新しいコントロールトークンが１個づつ出
力される。ノードと出力アークを組合せたものは、従来
の計算機の命令語に相当する。１つのノードに入力され
るべきコントロールト−クンは１図のＴＰで示されるよ
うに、それらのコンＩ・ロールトークンが人力されるべ
きノードへのポインタ　（ＮＰＲ）　　とともに１まと
めにされた形（トークンバケットＴＰと呼ばれる）で、
ノードドライブレジスタに格納される。ノード内の処理
が実行されることは、ノードが実行されるともいわれる
。このプログラムでは。
ノードＮ１が実行された後、　　Ｎ２．Ｎ３−Ｎ４−Ｎ
５−Ｎ６の順番に処理が行なわれる。ノードＮ２とＮ３
のうち２　どちらが先に実行されるかは、プログラムに
よって決められておらず、この順序は実行時に決定され
る。
本発明を第２図、第３図に示す実施例によって示す、第
２図は本コンピュータの構造を示す図である。ＰｔＪ１
〜ＰＬ１ｍは処理を行うためのｍ台のプロセッサ、ＭＭ
は主メモリ、ＮＤＲは本発明の特徴であるノードドライ
ブレジスタである。　ＭＭとＮＤＲは全プロセッサが同
時にアクセス可能なマルチボートメモリである。ＭＭに
はプログラムとデータなどが格納される。
ＮＤＲは１ワードよりなっており、各ワードの構成は第
３図に示すようになっている。ＮＰＭは。
トークンバケットＴＰ内のノードポインタＮＰＲの格納
場所であり、ＴＣＩ〜Ｔ　Ｃｎはコントロールトークン
の格納場所である。ＴＳは、このワードの状態を示すた
めに用いられる。ＴＣＩ〜ＴＣｎはカウンタより構成さ
れており、コントロールトークンが１個格納されるごと
に１づつ増加し、取り出されごとに１づつ減少する。Ｎ
ＤＲ内では。
実行可能なノードを示すために、同じツートポイタを持
つトークンバケットは１まとめにされて格納されなｉ′
３ればならない、そのため、ＮＤＲは１Ｎ　Ｐ　Ｍに書
かれたノードポインタによってアクセノすることができ
るように連想メモリ機能を持っている。
本実施例の基本動作は次のように行なわれる。
１）　プロセソサユニソｔ−ｐ　ｕは、ＮＤＲから。
１つのノードを実行するために必要なコントロールトー
クンが格納されているトークンバケット　（完全トーク
ンパケットＣＴＰと呼ばれる）を読む、このとき、この
ワードがアクセスされている最中であることを示すＴＳ
部のインジケータ■をオンにする。
２）　　ＰＵは、読み出したＣＴＰのＮＰＲ部から実行
可能なノードを知り、主メモリＭＭに格納されているそ
のノードを読んで、ノード内の処理を実行する。
３）　処理が完了したら２次に実行されるであろうノー
ドへのポインタとコントロールトークンを接続し、新し
いＴＰとしてＮＤＲに送る。このことは、実行されたノ
ードの出力アークに。
コントロールトークンを出力することに相当する。
４）　新しいＴＰを受は取ったＮＤＲは、そのＴＰＯＮ
ＰＲ部と同じノードポインタを持ったワードがＮＤＲ内
にあれば、そのワードに新しく、）ＴＰを格納し、すな
わち、同じノードポインタの値を持ったワードのＴＣｊ
（ｉ＝１〜ｎ−１のうちの１つの値）を１だけ増やし、
なければそのＴＰを新しいワードに格納する。この動作
は、ＮＤＲの連想機能を用いて行なわれる。これによっ
て、同一ノードに対するコントロールトークンが１まと
めにされる。
５）　すべてのＴＰを送り出したＰｔＪは、ステ・７ブ
１で読んだＴＰのインジケータＩをオフにし。
ＴＣＩ〜Ｔｃｊ　　（ｊは、このＴＰが送られるノード
によって決る変数で、そのノードの入カア−り数はｊで
ある）の値をｌｉｄしる。ステップ１に行く。
以上のステップは、すべてのプロセッサに対して行なわ
れるので、複数個のＣＴＰが読み出され。
複数個のノードが同時に実行される。
ＮＤＲは、連想機能を持ったマルチボートメモリである
ので、複雑になる可能性があるが１本コンピュータのプ
ロセソシングユニソトＰＵが、すべて同時に働（ために
最低限必要なＣＴＰの数はＰＵの数までであるので、Ｎ
ＤＲのワード数も特に膨大になるとは考えられず、大き
な問題とはならない。
本コンピュータでは、データフロー処理を行うことも可
能である。というのも、データフロー処理は、コントロ
ールトークンと共に、データもいっしょに流れなくては
ならないという、狭義のコントロールフロー処理である
からである。
以上のように１本発明によれば、簡単な構成で。
コントロールフロー、データフロープログラムの実行が
可能な並列処理コンビ二一夕を構成することができる。
【図面の簡単な説明】
第１図は、コントロールフロープログラムとトークンパ
ケットの関係を示す図で２図では１＝（ａ＋ｂ）（ｃ−
ｄ）＋ｅを計算するプログラムとなっている。第２図は
２本発明によるコントロールフロー並列計箕機の実施例
のブロック図、第３図は、ノードドライブレジスタの内
部構造を表わす図である。 図では、Ｎｌ−Ｎ６はノード、ＮＤＲはノードドライブ
レジスタ、ＰＵＩ〜ＰＵｍは、プロセッサ、ＭＭは主メ
モリである。 特許出願人 曽和将容

Claims (1)

    【特許請求の範囲】
  1. コントロールフロー並列計算機を構成するために、前記
    ノードドライブレジスタを設け、ノードドライブレジス
    タの各ワードに１同一ノードに関するコントロールトー
    クンと、そのノードに対するポインタとを格納すること
    によって、実行可能なノードを指示することを特徴とす
    るコントロールフロー並列計算機方式
JP58020863A 1983-02-10 1983-02-10 コントロ−ルフロ−並列計算機方式 Pending JPS59146345A (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
JP58020863A JPS59146345A (ja) 1983-02-10 1983-02-10 コントロ−ルフロ−並列計算機方式
EP84101399A EP0118781A3 (en) 1983-02-10 1984-02-10 Control flow parallel computer system
US07/147,128 US4809159A (en) 1983-02-10 1988-01-21 Control token mechanism for sequence dependent instruction execution in a multiprocessor

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP58020863A JPS59146345A (ja) 1983-02-10 1983-02-10 コントロ−ルフロ−並列計算機方式

Publications (1)

Publication Number Publication Date
JPS59146345A true JPS59146345A (ja) 1984-08-22

Family

ID=12038970

Family Applications (1)

Application Number Title Priority Date Filing Date
JP58020863A Pending JPS59146345A (ja) 1983-02-10 1983-02-10 コントロ−ルフロ−並列計算機方式

Country Status (3)

Country Link
US (1) US4809159A (ja)
EP (1) EP0118781A3 (ja)
JP (1) JPS59146345A (ja)

Families Citing this family (59)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS60101644A (ja) * 1983-11-07 1985-06-05 Masahiro Sowa ノイマン型コンピュータプログラムを実行するコントロールフローコンピュータ
JP2564805B2 (ja) * 1985-08-08 1996-12-18 日本電気株式会社 情報処理装置
US4903196A (en) * 1986-05-02 1990-02-20 International Business Machines Corporation Method and apparatus for guaranteeing the logical integrity of data in the general purpose registers of a complex multi-execution unit uniprocessor
US5029111A (en) * 1987-04-29 1991-07-02 Prime Computer, Inc. Shared bit-plane display system
US5010482A (en) * 1987-07-02 1991-04-23 Unisys Corp. Multi-event mechanism for queuing happened events for a large data processing system
GB8717689D0 (en) * 1987-07-25 1987-09-03 British Petroleum Co Plc Computers
US5247628A (en) * 1987-11-30 1993-09-21 International Business Machines Corporation Parallel processor instruction dispatch apparatus with interrupt handler
US5692139A (en) * 1988-01-11 1997-11-25 North American Philips Corporation, Signetics Div. VLIW processing device including improved memory for avoiding collisions without an excessive number of ports
JPH01188951A (ja) * 1988-01-23 1989-07-28 Sharp Corp データフロープログラムの実行制御方式
US5257392A (en) * 1988-01-29 1993-10-26 Sharp Kabushiki Kaisha System for loading and dumping data in a data flow processor based on paired program data and data to be processed
JP2752076B2 (ja) * 1988-02-23 1998-05-18 株式会社東芝 プログラマブル・コントローラ
WO1990001192A1 (en) * 1988-07-22 1990-02-08 United States Department Of Energy Data flow machine for data driven computing
US4964042A (en) * 1988-08-12 1990-10-16 Harris Corporation Static dataflow computer with a plurality of control structures simultaneously and continuously monitoring first and second communication channels
US5134705A (en) * 1988-10-21 1992-07-28 Unisys Corporation System and method for concurrency simulation
US5218706A (en) * 1988-12-19 1993-06-08 Mitsubishi Denki Kabushiki Kaisha Data flow processor with next destination node determination
DE68926043T2 (de) * 1989-07-20 1996-08-22 Toshiba Kawasaki Kk Mehrprozessor-Computersystem
EP0548074A1 (en) * 1989-08-21 1993-06-30 Massachusetts Institute Of Technology Distributed building of service request lists
USRE35311E (en) * 1990-04-04 1996-08-06 International Business Machines Corporation Data dependency collapsing hardware apparatus
US5809292A (en) * 1990-11-13 1998-09-15 International Business Machines Corporation Floating point for simid array machine
US5815723A (en) * 1990-11-13 1998-09-29 International Business Machines Corporation Picket autonomy on a SIMD machine
ATE180586T1 (de) * 1990-11-13 1999-06-15 Ibm Paralleles assoziativprozessor-system
US5765011A (en) * 1990-11-13 1998-06-09 International Business Machines Corporation Parallel processing system having a synchronous SIMD processing with processing elements emulating SIMD operation using individual instruction streams
US5794059A (en) * 1990-11-13 1998-08-11 International Business Machines Corporation N-dimensional modified hypercube
US5828894A (en) * 1990-11-13 1998-10-27 International Business Machines Corporation Array processor having grouping of SIMD pickets
US5588152A (en) * 1990-11-13 1996-12-24 International Business Machines Corporation Advanced parallel processor including advanced support hardware
US5752067A (en) * 1990-11-13 1998-05-12 International Business Machines Corporation Fully scalable parallel processing system having asynchronous SIMD processing
US5590345A (en) * 1990-11-13 1996-12-31 International Business Machines Corporation Advanced parallel array processor(APAP)
US5734921A (en) * 1990-11-13 1998-03-31 International Business Machines Corporation Advanced parallel array processor computer package
US5617577A (en) * 1990-11-13 1997-04-01 International Business Machines Corporation Advanced parallel array processor I/O connection
US5765012A (en) * 1990-11-13 1998-06-09 International Business Machines Corporation Controller for a SIMD/MIMD array having an instruction sequencer utilizing a canned routine library
US5625836A (en) * 1990-11-13 1997-04-29 International Business Machines Corporation SIMD/MIMD processing memory element (PME)
US5966528A (en) * 1990-11-13 1999-10-12 International Business Machines Corporation SIMD/MIMD array processor with vector processing
US5630162A (en) * 1990-11-13 1997-05-13 International Business Machines Corporation Array processor dotted communication network based on H-DOTs
US5963746A (en) * 1990-11-13 1999-10-05 International Business Machines Corporation Fully distributed processing memory element
US5765015A (en) * 1990-11-13 1998-06-09 International Business Machines Corporation Slide network for an array processor
US5963745A (en) * 1990-11-13 1999-10-05 International Business Machines Corporation APAP I/O programmable router
US5594918A (en) * 1991-05-13 1997-01-14 International Business Machines Corporation Parallel computer system providing multi-ported intelligent memory
JP2642039B2 (ja) * 1992-05-22 1997-08-20 インターナショナル・ビジネス・マシーンズ・コーポレイション アレイ・プロセッサ
US5809270A (en) * 1992-06-30 1998-09-15 Discovision Associates Inverse quantizer
US5784631A (en) 1992-06-30 1998-07-21 Discovision Associates Huffman decoder
DE69229338T2 (de) * 1992-06-30 1999-12-16 Discovision Associates, Irvine Datenpipelinesystem
US5768561A (en) * 1992-06-30 1998-06-16 Discovision Associates Tokens-based adaptive video processing arrangement
US6112017A (en) * 1992-06-30 2000-08-29 Discovision Associates Pipeline processing machine having a plurality of reconfigurable processing stages interconnected by a two-wire interface bus
US6435737B1 (en) 1992-06-30 2002-08-20 Discovision Associates Data pipeline system and data encoding method
US6330665B1 (en) 1992-06-30 2001-12-11 Discovision Associates Video parser
US6067417A (en) * 1992-06-30 2000-05-23 Discovision Associates Picture start token
US7095783B1 (en) 1992-06-30 2006-08-22 Discovision Associates Multistandard video decoder and decompression system for processing encoded bit streams including start codes and methods relating thereto
US6047112A (en) * 1992-06-30 2000-04-04 Discovision Associates Technique for initiating processing of a data stream of encoded video information
JPH06162228A (ja) * 1992-11-26 1994-06-10 Sharp Corp データフロープロセッサ装置
US5805914A (en) * 1993-06-24 1998-09-08 Discovision Associates Data pipeline system and data encoding method
US5984512A (en) * 1994-07-29 1999-11-16 Discovision Associates Method for storing video information
US5812741A (en) * 1996-02-14 1998-09-22 Jack Kennedy Metal Products And Buildings, Inc. Serial sequencers connected in parallel
CN1154060C (zh) * 2000-07-18 2004-06-16 徐肇昌 一种基于分布结构的并行模块结构及并行处理方法
US7350055B2 (en) 2004-10-20 2008-03-25 Arm Limited Tightly coupled accelerator
US7318143B2 (en) * 2004-10-20 2008-01-08 Arm Limited Reuseable configuration data
US7343482B2 (en) * 2004-10-20 2008-03-11 Arm Limited Program subgraph identification
US20080005357A1 (en) * 2006-06-30 2008-01-03 Microsoft Corporation Synchronizing dataflow computations, particularly in multi-processor setting
US9092212B2 (en) 2007-05-31 2015-07-28 James Arthur Dean Wallace Anderson Processors
KR20100084605A (ko) * 2007-05-31 2010-07-27 더 유니버시티 오브 레딩 프로세서

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4051551A (en) * 1976-05-03 1977-09-27 Burroughs Corporation Multidimensional parallel access computer memory system
US4228496A (en) * 1976-09-07 1980-10-14 Tandem Computers Incorporated Multiprocessor system
US4387427A (en) * 1978-12-21 1983-06-07 Intel Corporation Hardware scheduler/dispatcher for data processing system
US4414624A (en) * 1980-11-19 1983-11-08 The United States Of America As Represented By The Secretary Of The Navy Multiple-microcomputer processing
US4394727A (en) * 1981-05-04 1983-07-19 International Business Machines Corporation Multi-processor task dispatching apparatus
JPS57187755A (en) * 1981-05-13 1982-11-18 Masahiro Sowa Data driven computer system
US4491937A (en) * 1982-02-25 1985-01-01 Trw Inc. Multiport register file
US4525778A (en) * 1982-05-25 1985-06-25 Massachusetts Computer Corporation Computer memory control
US4553203A (en) * 1982-09-28 1985-11-12 Trw Inc. Easily schedulable horizontal computer

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
IEEE TRANSACTIONS ON COMPUTERS=1982US *

Also Published As

Publication number Publication date
EP0118781A2 (en) 1984-09-19
US4809159A (en) 1989-02-28
EP0118781A3 (en) 1987-10-28

Similar Documents

Publication Publication Date Title
JPS59146345A (ja) コントロ−ルフロ−並列計算機方式
JP2502960B2 (ja) マイクロコンピュ−タ、ならびにマイクロコンピユ−タおよびマイクロコンピユ−タ・ネットワ−クを動作させる方法
US5715435A (en) Trace control circuit in emulation system
US5276822A (en) System with enhanced execution of address-conflicting instructions using immediate data latch for holding immediate data of a preceding instruction
JP2752076B2 (ja) プログラマブル・コントローラ
GB2189910A (en) Motor speed control system
JPH0831033B2 (ja) データ処理装置
JPS6242301B2 (ja)
JPS61255422A (ja) タイマ制御回路
JPS61177540A (ja) ストリングデ−タ制御回路
JPH0743649B2 (ja) 演算回路
JPS6250855B2 (ja)
JPH0264828A (ja) アドレストレース回路
JPH0221331A (ja) マイクロコンピュータのプログラム制御方式
JPS61182135A (ja) 処理選択方法
JPS6111493B2 (ja)
JPH0228724A (ja) 分岐命令制御方式
JPS6238748B2 (ja)
JPH0580691B2 (ja)
JPH0812609B2 (ja) マイクロプロセッサ
JPH04147350A (ja) マイクロプログラムステップ出現回数計数方式
JPH05173779A (ja) デジタル演算集積回路
JPS63186372A (ja) ベクトル処理装置
JPH0318771B2 (ja)
JPH0439097B2 (ja)