金田の論文

金田 泰, 第 26 回プログラミング・シンポジウム報告集, pp. 47-56, 1985.

[ English page ]
[ 論文 PDF ファイル (2 MB) ]

要旨なし．

解説 : 並列計算機やスカラ処理のパイプライン計算機による Prolog の高速実行に 関してはおおくの研究があるが，この論文はいわゆるスーパー・コンピュータ すなわちベクトル型のパイプライン計算機によって論理型言語を高速化する ことをめざした最初の提案である． この論文は方式をしめしただけだが，その後の 研究によって一定の範囲のプログラムに関して，それが実現されている．

研究テーマ紹介: 論理 / 記号 ベクトル処理

金田 泰, 情報処理学会プログラミング言語研究会, PL-87-12, 1987.

[ English page ]

要旨:
ベクトル計算機 (スーパ・コンピュータ) による論理型言語プログラムの
高速実行方式の研究の一部として，OR ベクトル実行方式 (一種の OR 並列実行
方式) の研究をおこなっている． OR ベクトル実行方式にはマスク演算方式，
インデクス方式，圧縮方式の 3 種類があるが，これらをそれぞれ詳細化し，
N クウィーン問題をとくプログラムに適用した． すなわち，原始プログラム
を論理型言語による中間語にプログラム変換したのち Fortran と Pascal とに
ハンド・コンパイルし，日立 S-810 による実行性能を測定した． その結果，
どの方式でも 8 クウィーン全解探索の時間は 20 ms 弱，大型汎用計算機の
8 ～ 9 倍の性能であり，ベクトル計算機における各実行方式の有望性が
確認できた．

研究テーマ紹介: 論理 / 記号 ベクトル処理

Torii, S., Kojima, K., Kanada, Y., Sakata, A., Yoshizumi, S., and Takahashi, M., 4th Int'l Conf. on Data Engineering, pp. 194-201, 1988.

[ English page ]

研究テーマ紹介:
論理 / 記号 ベクトル処理

鳥居 俊一, 小島 啓二, 金田 泰, 坂田 明治, 吉住 誠一, 高橋 政美; 電子情報通信学会研究報告, DE88-8, pp. 57-64, 1988.

[ English page ]

Kanada, Y., Kojima, K., and Sugaya, M., ACM International Conference on Supercomputing, 539-549, St. Malo, 1988.

[ English page ]
[ 論文 PDF ファイル ]

要旨 (英語のみ): Several techniques for running Prolog programs on pipelined vector processors, such as the Hitachi S-820 or the Cray-2, are developed. This paper presents an automatic program transformation (vectorization) method of Prolog, which enables a type of or-parallel execution of Prolog programs using vector operations. Performance is evaluated on the Hitachi S-810 using the Eight-Queens Problem. Its vector execution speed is 4.5 MLIPS (18 ms). This is eight or nine times faster than scalar execution. This result confirms the effectiveness of vectorization techniques and applicability of vector prodcessors to Prolog execution and symbol processing applications.

研究テーマ紹介: 論理 / 記号 ベクトル処理

金田 泰, 小島 啓二, 菅谷 正弘, 情報処理学会論文誌, Vol. 29, No. 10, pp. 985-994, 1988.

[ English page ]
[ PDF 版論文へのいりぐち (IPSJ) ]

要旨: この論文では，探索問題に適用することができる，ベクトル計算機むきの あたらしい計算法並列バックトラック計算法をしめす． この方法にしたがって Fortran でプログラムを記述すれば， 数値計算専用とかんがえられていた S810 のようなスーパ・ コンピュータや，M-680H IAP/IDP (内蔵型アレイ・プロセッサ / 内蔵型データベース・プロセッサ)のようなベクトル計算機構を 付加した汎用計算機で，広範囲の探索問題を高速に実行することが できるまたこの方法では，並列度を適切に制御することによって， 必要な記憶量を逐次計算法とひとしいオーダにおさえることができる． この計算法をNクウィーン問題に適用し，つぎのような性能をえた． エイト・クウィーンの全解探索においては S-81O で逐次処理の約 9 倍，M-680H IAP および IDP を使用して約 1.7 倍だった． また，S-810 においては N ≧ 14 のとき単解探索でも逐次処理より 高速になった． これによって並列パックトラック計算法の有効性が たしかめられるとともに，ベクトル計算機 S-810 および M-680H IAP/IDP の記号処理への適用可能性がしめされた． また， 並列バックトラック計算法は，Prolog のような論理型言語の ベクトル計算磯による高速実行の可能性を示唆している．

研究テーマ紹介: 論理 / 記号 ベクトル処理

金田 泰, 菅谷 正弘, 情報処理学会論文誌, Vol. 30, No. 4, pp. 495-506, 1989.

[ English page ]
[ PDF 版論文へのいりぐち (IPSJ) ]
[ この論文の内容は博士論文にふくまれています．]

要旨: ベクトル計算機 (スーパ・コンピュータ) を使用して 論理型言語プログラムを並行処理するための一種の プログラム変換法 (ベクトル化法) を開発した． このベクトル化法は，OR 並列性があり，引数の入出力モードが 確定しているプログラムを対象とする． この方法では， 原始プログラムの論理変数ごとに，それが探索木上の ことなる位置でとる複数の値を各要素とするベクトルを つくり，それをベクトル処理するプログラムを生成する． この方法を N クウィーン問題のプログラムに適用して自動変換し， 生成されたプログラムがただしく動作することを確認すると ともに，ベクトル計算機 S-810 において 2.6 MLIPS という高い実行速度をえた．

研究テーマ紹介: 論理 / 記号 ベクトル処理

金田 泰, 菅谷 正弘, 情報処理学会論文誌, Vol. 30, No. 7, pp. 856-868, 1989.

[ English page ]
[ PDF 版論文へのいりぐち (IPSJ) ]

要旨: この論文では，ベクトル計算機を使用してリスト処理を高速に 実行するための基本戦略を提案する． この戦略は，Fortran プログラムのベクトル化技法の拡張と考えることができる 「くりかえし構造の交換」 と 「くりかえし構造の一重化」 というプログラム変換技法にもとづいている． 変換結果の プログラムにおいては，複数のリストを要素とするベクトルを 使用する． それらに関する操作をベクトル計算機のリスト・ ベクトル処理機能や数列生成機能などを用いて実現する． 上記の戦略をエイト・クウィーン問題の Prolog プログラムに 適用し，ベクトル計算機 S-810 においてスカラ処理の約 9 倍の実行速度をえた．

研究テーマ紹介: 論理 / 記号 ベクトル処理

Kanada, Y., and Sugaya, M., International Joint Conference on Artificial Intelligence '89, pp. 151-156, 1989.

[ English page ]
[ 論文 PDF ファイル ]

要旨 (英語のみ): This paper describes a technique for executing logic programming languages such as Prolog for the Cray-type vector processors. This technique, which we call the parallel backtracking technique, enables a kind of or-parallel execution without process explosion. The compiled intermediate language code for the parallel backtracking execution is the same as the code presented in our previous paper. The compilation is based on a kind of program transformation called or-vectorization. However, the interpretation of the intermediate code is changed to enable the parallel backtracking execution. An execution simulator and a compiler prototype were developed. We have not yet implemented this technique to our native code execution system, but we expect a performance of eight times or more higher than scalar processing upon implementation.

研究テーマ紹介: 論理 / 記号 ベクトル処理

Kanada, Y., PARBASE-90, IEEE, pp. 147-151, 1990.

[ English page ]
[ 論文ポストスクリプト・ファイル ]
[ 論文 PDF ファイル ]
[ IEEExplore 論文ページ ]

要旨 (英語のみ): This paper presents a vectorized algorithm for entering data into a hash table. A program that enters multiple data could not be executed on vector processors by conventional vectorization techniques because of data dependences. Our method enables execution of multiple data entry by conventional vector processors and improves the performance by a factor of 12.7 when entering 4099 pieces of data on the Hitachi S-810, compared to the normal sequential method. This method is applied to the address calculation sorting and the distribution counting sort, whose main part was unvectorizable by previous techniques. It improves performance by a factor of 12.8 when n = 2^14 on the S-810.

研究テーマ紹介: 論理 / 記号 ベクトル処理

金田 泰, 菅谷 正弘, 情報処理学会第 41 回全国大会, 1990.

[ English page ]

研究テーマ紹介:
論理 / 記号 ベクトル処理

金田 泰, 菅谷 正弘, 情報処理学会第 42 回全国大会, 4M-2, 1991.

[ English page ]

研究テーマ紹介: 論理 / 記号 ベクトル処理

Kanada, Y., International Conference on Supercomputing '91, Albuquerque, 1991.

[ English page ]
[ 論文 PDF ファイル (ACM DL) ]
[ 論文 PDF ファイル (一部フォント不正)] [ 論文ポストスクリプト・ファイル ]
[ これは 13. の論文のふるい版です．]
[ IEEExplore 論文ページ ]

[ この論文の内容は博士論文にふくまれています．]

要旨 (英語のみ): The conventional processing techniques for pipelined vector processors such as Cray-XMP, or SIMD parallel processors, such as CM-2 (connection machine), are generally applied only to independent multiple data processing. This paper describes a vector processing method of multiple processings including parallel rewriting of dynamic data structures with shared elements, and of multiple processings that may rewrite the same data element two or more times. This method is called the filtering-overwritten-label method (FOL). FOL enables vector processing of entering multiple data into a hash table, address calculation sorting, and many other algorithms that handle lists, trees, graphs and other types of symbolic data structures. FOL is applied to several symbolic processing algorithms; consequently, the performance is improved by a factor of ten on the Hitachi S-810.

研究テーマ紹介: 論理 / 記号 ベクトル処理

金田 泰, 菅谷 正弘, ソフトウェア科学会 8 回大会, 1991.

[ English page ]
[ この論文の内容は博士論文にふくまれています．]

研究テーマ紹介: 論理 / 記号 ベクトル処理

金田 泰, 東京大学大学院工学系研究科情報工学専門課程 博士論文, 1992.

[ English page ]
[ Kindle 版: ベクトル記号処理法とその論理型言語プログラムへの適用 ]
[ PDF 版論文の目次 ]

記号処理プログラムのベクトル処理法や論理型言語プログラムの自動ベクトル化 (Cray-1 タイプの計算機へのあてはめ) の方法を開発した．
-- SIMD 型の自動並列化をかんがえるときは，いまでも，ここからえられる ものがあるのではないかとかんがえている．

研究テーマ紹介: 論理 / 記号 ベクトル処理

Kanada, Y., Parallel Computing, Vol. 19, 1993, pp. 1155-1175.

[ English page ]
[ 論文 PDF ファイル (一部フォント不正)]
[ 論文ポストスクリプト・ファイル ]

要旨 (英語のみ): Conventional processing techniques for pipelined vector processors such as the Cray-XMP, or data-parallel computers, such as the Connection Machines, are generally applied only to independent multiple data prcessing. This paper describes a vector processing method for multiple processings including parallel rewriting of dynamic data strutures with shared elements, and for mutiple procesings that may rewrite the same data item multiple times. This method enables vector processing when entering mutiple data items into a hash table, address calculation sorting, and many other algorithms that handle lists, trees, graphs and other types of symbolic data structures. This method is aplied to several algorithms; consequently, the peformance is improved by a fator of ten on a Hitachi S-810.

研究テーマ紹介: 論理 / 記号 ベクトル処理

鳥居 俊一, 小島 啓二, 金田 泰, 坂田 明治, 高橋 政美, 情報処理学会論文誌, Vol. 34, No. 1, pp. 109-119, 1993-1.

[ English page ]
[ PDF 版論文へのいりぐち (IPSJ) ]

要旨: 本論文では，ベクトルアーキテクチャをマ一ジ演算に拡張した 内蔵データベースプロセッサ (IDP) を用いた非数値処理高速化の 課題と実例を示す． マージ型ベクトル演算は，各オペランドが 独立にインデックスを持つ点に特長がある． そのため，主記憶上に オペランドを置く必要があり，従来のベクトル演算以上に次の点で 性能上の課題がある． (1) 命令の立上りが遅い， (2) キャッシュ等の階層記憶機構への対応，(3) ベクトル化のオーバヘッドの考慮． 3 個の例題におけるベクトル化の 課題と高速化の効果について，具体的な実験結果を報告する． 関係データベースでは，複数の検索条件のある問合せ処理に適用し， 複数のインデックス利用方式により 4 倍の高速化を実現した， ソートユーティリティでは，2 ウェイのマージ命令を用いて マルチウェイのマージをベクトル化し，4 倍高速化の結果を得た． 解探索の N クィーン間題においても，2 倍の高速化を達成できた．

研究テーマ紹介: 論理 / 記号 ベクトル処理