並列・分散処理とは？ | 並列処理ソフトウェア | 並列処理アーキテクチャ
大量の計算処理を行うとき、1台の計算機でその処理すべてを行おうとすると、 非常に大変であり時間もかかってしまいます。そこで、処理を分割して何台か の計算機を使い、同時進行で処理を行うことにより全体の処理時間が短縮でき ます。これを並列処理といいます。
計算機クラスタ
並列計算機のひとつ。安価な計算機を多数用意し、これらをEthernetなどの ネットワークで結合することで並列計算機を構成します。したがって、比較的 安価でありながら高い性能を得ることができます。
大町研究室の計算機クラスタ 本研究室の計算機クラスタは、 Intel Pentium III800MHz(Dual)を搭載した計算機と Intel PentiumIII 500MHz(Dual)を搭載した計算機 をGigabitethernetで結合しています。 
負荷分散・タスク割当てアルゴリズム
並列処理を行う際、計算負荷と通信を適切に分散させる必要があります。大町研究室では、非一様な環境を対象としたタスク割当てアルゴリズムを開発しました。
特定のアプリケーション／アルゴリズムの並列化
計算機クラスタ上で効率的に特定の処理を実行するための並列実装を行っています。
- 2次元FFT（高速フーリエ変換）
- ニューラルネットワークの誤差逆伝播学習法
並列コンパイラ
処理の高速化には、キャッシュのヒット率を高めることが重要です。ループ プログラムを変換することにより、ヒット率を高める手法を研究しています。
シストリックアレーに関する研究
シストリックアレーとは、セルを規則正しく配列し、データをパイプライン的に流し込むことで、並列計算を行うアーキテクチャです。VLSI化に適しています。
特定用途向け並列アーキテクチャ
ここからはもっと詳しく
負荷分散・タスク割当てアルゴリズム
- 非均一環境におけるタスク割当てアルゴリズム
計算機クラスタは、任意の構成が可能であり、スケー ラビリティにも優れているという利点があります。しかし、任意の構成が可能 であるためにプロセッサの能力やネットワークが非均一である事も考えられま す。
そこで、各タスクの計算量や通信量、各プロセッサの能力や各プロセッサ間の距 離が任意である場合のタスク割当てを高速・高精度に求める手法を開発しました。- 並列ネットワークにおける動的負荷分散方式に関する研究
並列処理システムで効率よく処理を実行するには、負荷分散が非常に重要に なってきます。負荷分散とは、並列処理システム上に割り当てられた仕事の不 均衡によって生じるシステム全体のパフォーマンスの低下を、過負荷な計算機 の負荷を別の計算機に移送することで防ごうとするものです。負荷分散を適切 に行うことで、並列処理システム全体の利用率が向上し、処理速度の向上が期 待できます。
負荷分散の方式には、静的負荷分散と動的負荷分散の二つの方式があります。
本研究室では、並列処理プロセッサの負荷分散アルゴリズムとして、動的負荷 分散の手法である反復改良アルゴリズムに注目し、tree,CCC構造ネットワーク によって構成される並列処理システムの負荷分散に適したアルゴリズムの改良 を行いました。特定のアプリケーション／アルゴリズムの並列化
- ニューラルネットワークの誤差逆伝播学習法
ニューラルネットワークは多数の神経細胞とその結合の挙動をモデル化する ものであり、その処理に要する計算量は一般に多大なものとなってしまいます。 ニューラルネットワークのひとつである多層パーセプトロンとその学習法であ る誤差逆伝播学習法を並列計算機に効率的に割り当てることで高速化を実現し ました。
シストリックアレーとは
シストリックアレーは単純計算を行う素子（セル）を規則正しく配列し、計 算に要するデータをパイプライン的に流し込むことによって並列計算を行うものです。構造が一様であるため拡張性に優れ、また通信が局所的であるためVLSI化に適しているといった利点があります。シストリックアレーの設計理論
人があるプログラムから発見的にシストリックアレーを生成するのは非常に大変です。そこでシストリックアレーの自動生成が必要とされます。本研究室ではシストリックアレーの設計理論とシストリックアルゴリズム開発支援システムを開発しました。
与えられたループプログラムから、等価な計算を行なうシストリックアレーを半 自動生成します。
左図（上）のループプログラムから左図（下）のシストリックアレーを自動生成します。
赤い部分は、現在演算が行われている素子を表しています。
上からa[i,k]の値を、左からb[i,k]の値をそれぞれ流し込みます。さらに右下からc[i,j]を流し込みます。
左上から計算されたc[i,j]が出力されます。
- シストリックアレーの効率的構成法に関する研究
シストリックアレーを構成するにあたって、与えるプログラムに対して、複数種の構成が考えられ、どの構成が最良であるかという問題が発生します。そのため、いかに構成の結果が効率的になるように設計するかが重要になります。
本研究室ではシストリックアレーの構成の評価について考察し、計算時間を小さくできる構成法を開発しました。特定用途向け並列アーキテクチャ
- LZ77符号化並列処理アーキテクチャ
ロスレス圧縮としてよく用いられるLZ77符号の圧縮伸張を行うVLSIアーキテクチャを開発しました。
コンピュータ技術の進歩に伴う、大量の情報の伝送、蓄積の要求のもとで、有限な資源をより効率的に活用するため、VLSI/ULSI技術による専用ハードウェアを用いた高速データ符号化／復号化(圧縮／解凍)法が必要とされています。
データ符合化／復号化法には様々なものが存在しますが、本研究室では、数あるデータ符合化法のうちの一つであるLempel-Ziv符合化法、特にLZ77符合化法(この手法の改良型であるLZSS符号がLHAやgzipの中で用いられています)について、並列処理技術を採用しつつ、現在提案されているような形でのシストリックアレーを用いた提案法とは違ったスタンスからの高速Lempel-Zivデータ符合化シストリック・アーキテクチャを開発しました。
開発したシストリックアーキテクチャ - フラクタル画像圧縮・伸張アーキテクチャ
フラクタル画像符号化を行うVLSIアーキテクチャを開発しました。
近年、JPEG，MPEGのような画像圧縮の研究が盛んに行われています。画像圧縮の応用としては、ファイルの伝送、ビデオ会議、携帯電話からの画像伝送、テレビ放送の伝送などがあります。最近、フラクタル画像圧縮というものがありますが、それはBarnsleyとJacquinが反復関数システムに基づいて提案した画像圧縮方法です。元画像をその画像の中にある自己相似画像に近似するものです。
フラクタル画像圧縮の大きな問題は符号時間が膨大になることです。その問題を専用ハードウェアを使う事で解決しようとしている研究があります。いくつか提案されていますが、それらの特徴はドメインのための外部メモリをもったり、Globalデータ通信を使ってメインメモリからドメインを呼び出す方法を取っています。これは、もし、プロセッサが増えるとシステム全体のスピードが落ちる問題があります。
フラクタル画像圧縮のイメージ そこで、本研究ではフラクタル画像圧縮アルゴリズムの改良として、VLSI設計に有効な新しい分割法を提案しました。また、並列処理アーキテクチャとして、固定サイズ分割法と4分割法のためのアーキテクチャを提案しました。その特徴は、シストリックアレーの構造で、ドメインの外部メモリがなく、Localデータ通信だけを使うもので、回転鏡像ドメインの距離計算を高速にするModuleを持っていることです。
開発したアーキテクチャ
