チューナブル・アーキテクチャ計算機システムにおけるチューニング過程について

　 MEMoms 　OF 　5▲ G▲ Ml IN餌T ：丁叮1圏 OF 　T］CHNOLOGT 　 　 Vo1

．

烈）

，

　No

．

1

，

1986

チ

ュ

ー ナ

ブ

ル

・

ア

ー

キ

テ ク

チ _ャ

計

算 機

シ ス テ ム

に

お

け

る

　　　　　　

チ

ュ

ー

ニ ン

グ

過

程

に

つ い

て

深

沢

良 彰

＊

・

岸 野

　覚

＊ ＊

・

門 倉

敏 夫

＊ ＊

ATuning

　

Process

　

in

　a　

Tunable

　

Archtecture

　

Computer

　

System

Yoshiaki

　

FuKAzAwA

，　

SatQru

　

Kls

且INo　and 　

Toshio

　

KADoKuRA

　 　

Atuning

　process　in　a　tunable　archtecture 　computer 　is　described

．

　 　

We

　

have

　

designed

　a　computer 　system 　with 　tunable 　archtecture

．

　

Main

　components 　of　this　computer

are　four　AM 　2903　

bit−

slice　chips

．

　

The

　control 　schema 　of　micro 　

instructions

　

is

　

horizontal

・

type

，

　and 　 the length　of　each 　instruction　is　104　

bits．

　 　

Our

　tunable 　algorithm 　utilizes 　an 　execution 　history　of　machine 　

level

　instructions

，

　

because

　the

execution 　history　can 　be　regarded 　as　a　property　of　the　user　program

．

　

In

　execution 　

histories

　of　similar programs ，　 same 　 sequences 　 of　 machine 　

instructions

　must 　appear

．

　 Each 　sequence 　is　synthesized 　

into

　a

new 　machine 　instruction　by　means 　of　microprogramming

．

　 In　order 　to　select 　new 　machine 　instructions

，

this　algorithm 　uses 　not 　only 　the　enlarged 　amount 　of　necessary 　control 　storage 　

but

　also　the　

improvement

Of　eXeCUtiOn 　eMCienCy

．

1．

は じ め に 　 従 来の汎 用 計 算機は

，

広範囲の 問 題を平均 的な効 率で 実 行

，

処 理 するこ とを 目的 として設 計されて きた 。 とこ ろが

，

ユ

ー

_{ザは 計 算 機に対 し}

，

_{よ り高い処 理 能 力 を 求め} て きて い る。 こ の要 求に対 応 して

，

さ ま ざ ま な 専 用ア

ー

キ テクチ ャを もつ 計算 機が開発さ れ てきた。 し か し なが ら

，

こ の ような専用ア

ー

キテ ク チ ャ をもつ 計算機の性能 を十 分に発揮で ぎる応 用 問 題は限 られて い る の_{が 現 状}で

ある。 例 えば

，Floating

　

Point

　

Systems

社の

AP −120BD

は

，

フ

ー

リエ 変換を も ちい た応用問 題に対 し て し か優れ た性能を 示 さ ない 。 　我々は汎 用 性 を 重 視し， 対 象 とする応 用 問題は限 定せ ず

，

同種の問題 が繰 り返し実 行される場 合に処理効 率が 向上 して い く計 算 機 シ ス テ ム _{を設 計し た。 本}シ ス テ ム は

，

機 械 語の 実 行 履 歴を解析し

，

まず

，

出 現 する命令列 すべ てを 1命令に 合 成し

，

その 中か ら適当な命令 （合成 ＊ 情 報工 学 科 　 講 師 　＊ ＊ 早稲田大 学理 工 学 部 　

1985

年

10

月

30

日受 付 命令） を選択 するこ とに よ り実 行 効 率の向 上をは か るも の で ある。 　 本論文で はチ ュ

ー

ニ ン グのた めの ア ル ゴ リズ ムお よ び シ ミ

ュ

レ

ー

シ ョ ン に よ る結 果につ い て述べ る。

2

．

チ ュ

ー

＝ ングの概 要と特 徴 　プロ グ ラ ムが実 行された ときの機 械 語の 履歴は

，

処理 する問題の_特性であ ると考 え られ る。 そ して

，

同種の 問 題を 処 理する プロ グ ラム _{が 繰} り返 し実行される場 合

，

そ れらの実 行の履歴には， せ まい 範囲で見れ ばよく似た命 令 列が出 現し て い る と考えられ る。 こ の よ うな命 令 列 を 1つ の命令に合 成 し， 命 令セ ッ トに追 加 す れ ば， 実 行 効 率は向上 すると考え られる2） 。 　本 シ ス テム では

，

合 成 を 行な う命令 列の対 象と し て

_，

プロ _ヅ ク と隣接 命令を考えて い る。 　ブ ロ _ッ クと は

，

プ ロ グラ ムの制 御 フ 卩

一

に 注 目し て分 割さ れ た単 位である。 実 行の制 御は ブ ロ ッ クの先 頭命令 に渡 さ れ

，

ブロ _ッ クの最 後の 命 令は

，

制 御を他の ブ巨 _ヅ ク に移 す。 本 シ ス テムでの ブロ ッ クは

一

般の コ ン パ イ ラ

相 模工 業 大 学 紀 要 　 第

20

巻 　 第

1

号 がオ ブ ジェ ク ト

・

コ

ー

ドの最 適 化を行な うときに使 用 す る基 本ブ 卩 _ッ クS） とほ とん ど同じ であ る。 　 隣 接 命 令とは

，

ブロ ッ ク内で続けて実 行 さ れる命 令の ペ ア の こ とであ る。 　本 研 究 と目的 を 同じくする Abd

・

Alla らの 手法4）_は

_，

プ巨 _グラ ムのル

ー

プ だけに注 目し て ， これをマ イク ロ ・ プロ グ ラムで 合成し， 新しい 1 つ の 命 令にするこ とに よっ て， 実 行 効

率

の 向上 を目指 す もの である。 ま た

，

坂 村 らの 手 法S

−

6）_IX

_，

_{続 けて実 行 さ れ る命令の 出 現 頻 度だ} けに注 目す るもの で ある。 　 本チ

ュー

ニ ン グの特 徴は

，

隣 接 命 令とブ ロ _ッ クの出現 回数の他に 合 成

，

追 加 さ れ た 命 令に よっ て増 加 す る 制 御 記 憶の量 に も考 慮し

，

合 成された命 令の中か ら 適 当 な命 令 を 選 択 してい る点であ る。 これ に よっ て， 経 済的で効 率の 良い チ ュ

ー

＝ ソ グを 可 能 と し てい る。 本チェ

ー

ニ ン グ _{と 同 様}の手 法 を 用い たチ ュ

ー

ニ ング法の研究に坂村ら の 研 究T）_{があ るが} ， 命 令の選択に用い る評価関 数の 求め 方が異なっ てい る。 　 本チ ュ

ー

ニ ングを繰 り返し行な うこ と に よ り

，

対象と する問題に対 する機 械 語 レ ベ ル で の ア

ー

キ テ ク チ ャ の是 非を考察する こ とも 可 能である。

3

．

_本

シ ス テ ム の ハ

ー

ドウェ ア構 成の

概略

　本シ ステ ム _の

ハー

_{ド ウ}ェ ア は 既 存の マ イ クロ

・

プロ セ ッ サ （EP ）

．

と， ビッ ト・ ス ラ イス ・ チ ッ プ

AM

　

2900

シ リ

ー

ズe）_{を 用 い た}マ イ ク ロ

・

プロ グラ ム _{可 能 な}プロ セ ッ サ （

MP

）か ら 構 成 されて い る。 これ を 図

1

に 示 す。 　3

．

1． MP

の概 要 　 MP の_構成

，

　

MP

の マ _イ ク ロ _プ ロ _グラ ム につ い て 以 下 に_述ぺ る。 　

3．

1．

1． MP

の構 成 　 MP は ALU 部， プロ グ ラム 制 御部， デ

ー

タ パ ス 部，

1

！

0

イン タ

ー

フ ェ

ー

ス部

，

メモ リ制 御 部

，

制 御 記憶

，

主 記 憶か ら構 成さ れ てい る。 図2 に MP の構成 図を 示す。 　

ALU

部は

4

個の ビッ ト

・

ス ラ イス

・

チッ プ

AM2903

で構成されて い る

。

デ

ー

タ パ ス部には

，16

ピ _ッ ト の デ

ー

タ バ スを

4

ビ _ッ ト単 位で取 り出 すセ レ ク タ を 設 け， オペ ラソ ド圧縮を行なっ た命 令の実 行が 可能と な っ て い る_。 プロ _グラ ム_{制 御 部}は プ ロ _{グ ラ}ム

。

カ ウン タを 制御 する部 分で あ り

，

カ ウ ンタを

1

語 （

16

ビッ b） また は

2

語 増 減 するこ とが 可能で _ある。 制御 記 憶は書 き換え可能で あ 　 　 　

1

μP可能な計 算機 （MP ）　

’

既 存の計 算 機 （EP ）

　　　　　　　娼

　　　　　　　　　

1

　 　図 1 本シ ス テ ム の プ ロ セ ッ サ 構成 ADDRESS 　BUS DATA 　BUS DATAPATH 制御記 憶 主 記 憶 PCU ［Pr。9ramCo 冂trolUnltI

　　 ，

■

囓

■

匸

マ イク囗

・

コ

ー

ド ALU 「

1

／0イ ン タ

ー

フェ

ー

ス メ モ リ制 御 図 2 　MP の 構成 る。 マ イ クロ 。 プロ グ ラ ムは

，

デ

ー

_{タ バ ス を通 して} ロ

ー

ドさ れる

．

制 御 記 憶の 1 語は 104 ピ ッ ト で あり

，

容量 は

2K

_語である。 デ

ー

タパ ス部の構成 を 図

3

に示 す。 　3

．

1

．

2

．

MP

のマ イ クロ

・

プログ ラム 　マ イ クロ 命 令の形 式は間接水平型で あ り

，MP

の各 部 を柔 軟に 制 御 するこ と が 可能 である。 V イ ク ロ 命 令の フ _ォ

ー

マ _ッ トを図4 に示 す。 また， 命 令フ ェ ッ チ， 命 令 デコ

ー

ド_， オペ ラン ド ・ フ ェ ッ チ

，

命 令 実 行の 各フ ェ

ー

ズ はすべ て マ _イ ク ロ

・

プ ロ グラム で実現されて お り

，

プ ロ グ ラム の_実行 履 歴の 収 集 も

，

マ イ クロ

・

プロ グ ラムで 実 現して い る。

チ ュ

ー

ナ ブル ・ア

ー

キ テク チャ 計 算 機シ ス テム に おけるチュ

ー

ニ ン グ過 程につ い て （深 沢 良 彰・岸 野 　 覚・門 倉 敏 夫 ｝ DATA

　

BUS Z

−

Reg 16 16 ZO

−

Reg Z1

−

Reg8 EX

−

Re9 16 トReg SELECTOR ALL 「

’

₈

ZO

−

Reg　　　　MICRO

・

INST

．

DE

−

Reg　　　　　　　MUX

　．

，

■

闇M 4 　 　 　 DB 日US 44 DA 　BUS 　 　　　　　　　　 　　　　　　　　　 　　SELECTOR

尸

　 　 　 4 　 　 　 A

−

Port 図 3 デ

ー

タ パ ス の構 成 B

・

Port

ExtraSelector 　and 　Decode 　ControtALUData 　PathProgram 　ControlMemory 　Control

103

−

96

95−91

90

一

ア877

−65

64−54

53

−

49

Control　StrobesControl 　BitStatusTestSeque 冖ce　ControlNext 　Addres5＆l　lmmediate

48

−

43 42

−

35 34

−

2625

−

20 19

−

16 15

−

O 図

4

マ イ ク ロ _{命 令}の フ ォ

ー

マ ッ ト

4 ． 本

シス テ ム の流 れ 　本シ ス テ ム の 流れ を 図 5 に示す。 チ ュ

ー

ニ ン グは 以 下 の手 順に 従っ て行なわれる。 　（1＞ 対 象 と なる プロ グラム _を

EP

上 で

MP

_用に ク ロ ス

・

コ ソ パ イル， アセ ン ブル する。 　 （2）　 生 成した オ ブジ ェ ク ト

・

プPt グラ ム を MP 用 の主記憶に ロ

ー

ドし

，

実 行 する。 　（3）　 実行された機械語の ア ドレ ス が

，MP

の マ _イ ク ロ

・

プロ _グラ ム に よっ て

，

実 行 履歴 として 出 力 さ れる。 　 （4）　 実 行 履 歴が解 析さ れ て隣 接命令

，

ブ ロ ッ クそ れ ぞ れの出 現回数を出 力 する。 　 （5） ア セ ン _ブル _時に 生成 され る情 報 と あ らか じめ設 定 されてい るマ イ _ク ロ

・

プロ グラ ム の ソ

ー

スか ら

，

すべ て の隣 接命令

，

すべ _ての ブ ロ _ッ クに 対 して命 令合 成 が行 な わ れる。 　（6）　出 現回数

，

制 御記憶の_増加

，

実行時間の 向 上を 考 慮し た評価関 数 を 用い て 合 成 さ れ た 命 令の中から新 し く命令セ ッ ト に加え られるべ き機 械 語 が選択される。 　（7） 選 択 さ れ た命令のた めの マ _イク ロ

。

プ 卩 _{グ ラ} ム を初 期 設 定 さ れて い る マ イ ク ロ

・

プ ロ グラム に 組み込 み

，

統合 さ れ たマ イ ク 卩 ・ プロ グ ラ ムを生 成 する

。

　（8）　 命 令選択に よっ て選択された機械 語に関 する情 報は合成機 械語命令情報の_作成

，

更 新部に渡されるQ

相 模工 業大学紀 要　第 20 巻　第 1 号 図 5 本シ ス テ ム の 流 れ 　（9） 統合さ れ たマ _イ クロ

・

_プロ _グラ ム _はマ イ ク ロ ・ ア セ ン ブル_部で V イ ク ロ

・

プ ロ _{グ ラ}ムの オ ブ ジ

ェ

ク ト

・

コ

ー

ド_{に ア} セ ン ブル され，

MP

の制御記 憶に 卩

一

ドされ る。

　

（10） 次の 対象プロ グ ラムに つ いて （

1

）か ら繰り返 す。

5

_{． 本}

シ ス テ ム の

構

成 　本 シ ス テ ムは

，

コ ンパ _{イル 部}

，

_{ア セ ン ブル} 部

，

履歴解 析部

，

命令合 成部

，

命 令選択 部

，

V _イク ロ

・

プロ グラ ム 統 合 部から構 成さ れ てい る。 以 下， 各 部に つ い て説 明 す るo 　 5

・

1．

　コンパイル部 　コ ン パ イル _部は

，

_{高 水準言語}に よっ て記 述 された プ ロ グラ ムを 入力と し

，

ブ ロ _ッ ク情 報を含ん だ MP 用 の 初 期アセ ン ブ リ言語を出力 する。 ブP ッ ク情 報はア セ ン ブ リ言 語の ラ ベ ル と して出 力 され る

。

　

機 械語の中に_新た に生成された命 令を 真に組 み 込 むに は

，

多機 種 用 の コ

ー

ド_{生 成 系}9）_{を 利 用 して}

，

_{合 成命 令を} 含ん だオ ブジ

ェ

ク ト・ コ

ー

ド生 成 を 行 な う_{こ と}が_{望 まし} い 。 し か し， 本シ ス テ ム が行 な う命令合 成で は

，

コ ソ パ イル結果をアセ ンブ リ_{言 語}で 作 成し

，

ブ ロ _ッ ク_情報を出 力するコ ン パ イラがあ れば

一

応の評価が 可能な た め， こ の ような 構 成 とし た。 　

5・

2・

アセン ブル部 　コ ン パ イル _部が生 成し たア セ ソ ブ リ言語プ ロ グラ ム _を

MP

用の オ ブジ ェ ク ト・ プ Pt グラ ム とし て 出 力 する_。 　コ ン パ イル _部が生 成 するアセ ン ブリ言語は初期設 定 さ れ た命 令に 固 定 さ れてい る。 こ のた め

，

コ ン パ イル部 が 出 力 し たア セ ンブ リ言 語の プ卩 _グラ ム_{を合 成命 令を使}っ た プロ グラ ム に_{変更 す}る_{機 能}を もっ て い る。

　

ま た

ロ

ア セ ンプル 部はプ ロ _ヅ ク の先 頭ア ドレス

，

_{隣 接} 命令， ブ ロ ッ ク， そし て ア ドレ ス と機 械語との対 応 表 を 出 力 する。 　

5。

3．

履 歴 解 析部

　

履 歴 解析 部は

，MP

に よっ て実 行された機 械語の ア ド レ ス _{（実 行履歴）}

，

ブロ ッ ク， ブ ロ ッ ク の 先 頭ア ドレ ス， 隣 接 命 令

，

そ し て ア ドレ _{ス と機 械 語との対応表を 入力と} し

，

ブロ _ッ ク_{出現回数， 隣 接命令 出 現 回 数 を 出 力 する} 。 ア ドレ ス と機 械 語との対 応 表は， ア ドレ ス とし て格納 さ れ て い る実 行 履 歴か ら機 械語 を得る た めに使わ れ る。 　 この アル ゴ リ ズ ム _{を 以 下}に示 す。

do

　while （履 歴フ ァ イル が続く）； 　ア ドレ ス を 1つ _取 り出 す； 　

if

ア ドレ ス＝ ブロ _ッ ク の先 頭ア ドレ ス 　 　 then 　こ の ブロ _ッ ク_{出 現 回数を} 1_増 し

，

こ の ア ド 　 　 　 　 　レ ス か ら機 械 語を得て

，

_隣接命令の初めの 　 　 　 　 　命令とする ； 　 　else　

do

_； 　 　 　ア ドレ ス _を 1つ _{取 り出}し， こ の ア ドレ ス か ら機 　 　 　 械 語 を 得る； 　 　 　

if

ア ドレ ス ＝ ブロ ッ クの先 頭ア ドレ ス 　 　 　 then こ の ブロ _ッ ク 出 現回数を 1 増し

，

今得た

チ

ュー

ナ ブル

・

ア

ー

キテ ク チャ計 算機シ ス テ ム に お ける チ ュ

ー

ニ ン グ 過 程 につ い て （深 沢 良 彰・岸 野

　

覚

・

門 倉敏 夫 ）

　　　

機 械語は 隣接 命令の 初 め の 命令であると 　 　 　 する ； else

　

今 得た機 械語は隣 接 命 令の_終わ りの_{命 令}と 　 　 　し

，

その隣 接 命 令 出現回数を 1 増す； 　end ； end ； 　5

・

4

・

命令合成 部 　命令 合 成部は プ 卩 _ヅ ク

，

隣 接 命 令

，

前 回の チ

ュー

ニ ン グで 得 られ たマ _イ ク ロ

。

プ ロ グラ ム の ソ

ー

ス _を入 力 と し

，

すべ ての ブ ロ ッ ク

，

すべ て の 隣 接命令に 対し て合成 さ れ たマ _イ ク P

。

プロ グ ラ ム の ソ

ー

ス _{を 出 力 す}るQ 　命 令の 合 成は

，

デコ

ー

ド_部の合 成

，

実 行 部の合 成の順 で行 な われ る。 　デコ

ー

_ド部の合成におい て は

，

合 成 され た 命 令の オペ コ

ー

_{ド と}

，

_デ コ

ー

ドの 対 象 と なる命 令の オペ コ

ー

ドとを 比 較 するQ こ の両 者 が

一

致し た場 合に は合 成 され た命令 の 実 行へ _{制 御}を移すように デコ

ー

_{ド部 を}合成す_る 。 し か し， デコ

ー

ド部が合 成 さ れた段 階で は

，

合 成して い る命 令が命 令 選 択 部で合 成命 令として選 択 されるとは 限 ら な い ため

，

この命 令に対 する オペ コ

ー

ドは

，

決 定 するこ と ができない。 従っ て

，

こ の決 定は 命 令 選 択 部で行なっ て い る。

　

実行 部の合 成は次の

2

つ の手 法の ど ち ら かに よっ て 行 なわれるD

　

（1） 命 令圧縮を行 なわず

，

命 令の フ ェ ッ チ

，

デコ

ー

ドを減らす。 　（2） 命 令 圧 縮を 行 ない

，

命 令の フ ＝ ッ チ ， デコ

ー

ド_， オ ペ ラ ン ド

・

フ ェ ッ チ を減らす

。

　

（1）はマ _イ ク ロ

・

プ ロ グラム _中の シ

ー

ケ ソ サ_用命 令を 変 更 す るこ と に よ り実現 さ れる。 （2）は合 成の対 象と な る命 令 列に従 っ て， 種々 の 方法で行な われる。 （1）と（2） の例を 以下に示 す。

　

まず， （1）に よ る命令合 成の 例 を 示 す。 対象と な る命 令列と合 成された 命 令を

，

図 6に示 す。 （a）は デ n ス プ レ

ー

ス メ ン ト DATA に イ ン デ ヅ ク ス レジ ス タ X2 の

DRLA

SYN1

図

6

値を 加 え

，

その値 を実 効ア ドレ ス とし

，

その ア ドレ ス の 内 容をレ ジ ス タ 1に ロ

ー

ドす_る命 令である_。 （b）は レジ ス タ

2

とレ ジス タ

3

の 内容を加え

，

その_{結 果}の_格納場 所 が レ ジス タ 2 に なる 命 令 で _ある。 （c）は本シ ス テ ム に よっ て合 成された命 令で

，

（a）の 演 算と

，

（b）の演算を

1

命 令に よっ て行 な う もの で ある

。

シ ス テ ムは ＝

一

モ ニ ッ クと し て

，

こ こ では

SYN

　

1

を 与 えてい る。

　

（a_）に 対 するマ _イ ク P 命令中 の シ

ー

ケ ン サ 用命 令を SYN 　1 _{の オ} ベ _ラ ン ド R2 _，　R　3 _をフ

＝

ッ チする ため の サ LD 　RI

．

　X2 _（DATA ） 　 の実行 シ

ー

ケン ス LD？ NOYES 　 （デコ

ー

ド） Displacement Address の決 定 Call　Displacement 　 　 Fetch　Routine Operand 　Addre55 の 計 算 CalL　Operand 　Fetch

　 　 Routine 　 Routine AR 　R2

．

　R3 　 の実 行シ

ー

ケン ス ド） 　 　Routine

R1

，　

X2

（DATA ）　　　　　　　

…＿

（a ） R2

，

　 R3 

……

_（b_）

↓

　

R1

，　

X2

（DATA ）

，

　R　2

，

　R　

3

　

・

…・

・

（c） 合 成対象の 命令 列と その合 成 命 令 〈手法 （1）〉 図 7LD 命令 と AR 命 令の実 行 シ

ー

ケ ン ス 　 　 NOSYN 　 　

’

YES （デコ

ー

ド） ↓ Displacement Addre55 の決 定

Call　Displacement　Fetch　Routine

　Operand 　Addre55 の計 算

Call　Operand 　Fetoh　Routine

　　　　　R1

一

〇perand Call　Operand 　Fetch　Routine

　　　R2

・

一

匚R2P ［R3］

Jump 命 令 Fetch　Routine

膠

一 一

一

冖 ，

． 一

．

　　　　　　　命 令Fe しch　Routine LD 命令と 同じ R2

　

R3 の Fetch

　，

図 8 手 法 （1）に よ り合成 さ れ た命 令 SYN 　1 　 　 　の実 行シ

ー

ケ ンス

相 摸工 業 大 学紀要　 第 20 巻 　 第 1 号 ブル

ー

チ ン 。 コ

ー

ル に_変更 し

，

こ の後に （

b

）に対 するマ イ クロ

・

_プ ロ グ ラ ム _{を 結 合 し （}c_{） を 実 行 する}マ _イク ロ ・ プロ グラム が合成され るo （a）

，

（

b

｝の 実行 シ

ー

ケ ン ス を 図 7

，

（c_）の 実 行シ

ー

ケ ン ス を図 8 に示す。 　次に ， （2）に よ る命令合 成の例を 示す。 対 象と な る命 令 列と合 成された命 令を 図

9

に 示 す。 対 象 と なる命令 列， （

d

）

〜

（

f

）は レ ジス タ間で ロ

ー

ド

，

加 算， 減 算 を 行 な う命 令列で あ り

，

各々の結 果の格納 場 所で ある第

1

オペ ラ ン ド_{が 同}

一

である と仮 定 する。 そこ で

，

不 必要なオペ ラン ド情報 の排 除 を 行 ない

，

オ ペ _ラン ドを 圧縮し た命令 を 合 成 する。

　

デ

ー

タパ ス _中の セ レ ク タはこの ような命 令を実 行す る た めに ある。 セ レ ク タ の機 能は オペ ラ ン ドをバ ヅ フ ァ リ ン グ_するレ ジス タ の 出 力をビ _ッ ト_{単 位}で_取り出し，ALU へ _{出 力 するもの である} 。

　

（d）にあた るv イ クロ _命令の シ

ー

ケ ンサ_{用 命 令}がオペ RRR LAS R1 ，　

R2

R1 ，

　

R3

Rl

，　

R4

↓

…



響

・

・

_（d）

・

…・

・

_（e）

・

・

・

…

_（f）

SYN2

_R1

，

　R2

，

　

R3

_，　

R4



……

_（g） 図

9

合 成 対 象の命令列と その _{合 成 命 令 く}手 法 （

2

）〉 LR　Rl

，

R2 _{命 令}の実 行 　 　 　 シ

ー

ケン ス 　 Routine ARR1

_，

R3 _{命 令}の実行 　 　 　 　 シ

ー

ケン ス 　 Reutine 図

11

　手 法 （

2

）に よ り合成 さ れ た命 令 SYN 　2 の 　 　 　 実 行シ

ー

ケ ン _ス SRR1

_，

R4 命 令の実 行 シ

ー

ケン ス 　　 　 NOSR ？ 　　　YES 　　　　　　（デコ

ー

ド ）

　

　　一 一一一＿一

一

一

　　　　R

←

［Rl］

一

［R ］

Jum 　 命 令 Fetch　Routinθ

一 一

一 一

＿ 凾 辱一 一一 一

一 ●

一

　　命 令 Feteh　Ro凵t 図

10LR

命 令

，

　

AR

命令

，

　

SR

命令の _{実 行}シ

ー

ケ 　 　 　 ン ス ラ ン ド・ フ ェ ヅ チのた めの サ ブル

ー

チ ン呼び出 し に変 更 さ れ る。 これに よ り

SYN

　2 の オペ ラ ン ド R3 ，　R4 が バ _ッ フ ァ リン グレ ジス タ に ロ

ー

_ドされる 。 （e）に対 する V イ クロ 。 プロ グラ ム中のセ レ クタ制 御命令は ， オペ ラ ン _ドの 1_{つ と し て}

R3

_{を 取 り出 すよ うに変 更 される} 。 ま た

，

シ

ー

ケ ンサ用 命令は

，

次の マ イ_{ク Pt命 令に制御を} 移 す命 令に変 更され る。 （

f

）に 対 してはセ レ クタ制 御 命 令が

，

（e）と同 様に

R4

を出 力 する よ うに_変更 される

。

　（d）

，

（e）， （f）の 各 々の実 行シ

ー

ケ ン ス を 図

10

に

，

（g） の_{実 行}シ

ー

ケ ンスを 図

11

に示す。 　5

・

5

・

命 令 選 択 部

　

命 令選択部は ブ ロ _ッ ク出 現回数

，

隣接 命令出 現 回数

，

そして _合成 されたマ _イ クロ

・

_プロ _グラ ムの ソ

ー

ス を 入力 とし， 新しく命令セ ッ ト に加 えるべ き機 械 語と その 情 報， そ して その た め の マ イ クロ プロ グ ラム を 出 力 する。 選 択の ため の評価関 数は次にあげる

Fm

を 用い る。 　 　 　 　

Fm ＝

塩

・

」

7

諞μ

s

皿 　 　 　m ：ある隣接 命令ま た は

，

ある ブ 卩 _ッ ク 　 　

Km

： m の 出 現 回 数 　 　

ATm

：m に よ る実行時 間の 向上分

　　 riSm

　： m に よる 増 加 制 御 記 憶 分 （時 間に_{換 算}） 　

dTm

と

ASm

は

，

マ イ クロ

・

プ ロ グ ラ ム の ス テ ッ プ 数に 1マ _イ クロ 命_令の実 行 時 間を乗 じて求め てい る。 こ れ は

，

時 間を動 的に調べ _るこ とが不可 能な ため で ある。

チ ＝

＿

ナカ レ

．

ア

ー

キ テクチ 。計 算 機シス テ ム にお けるチ ・

一

ニ ン グ過程につ い て （深 沢良 彰

・

岸野 覚

’

門 倉敏刔 そこで

，

静的に正 確に わか らない 部 分 を 近 似し て求めて い る。 例えぽ

，

デ コ

ー

_{ド時 間に}関_して ば

，

デコ

ー

ド_用の マ _イ ク ロ

・

_プロ _グラ ム量の 半 分を時 間に換算し

，

マ _イ ク ロ ・ プ卩 グラ ム

・

レ ベ ル での条 件 分 岐に対 し て は

，

最 悪 経 路 と最 良 経 路の和の 半 分の マ _イ クロ 。 プロ グラ ム_{量 を} 時 間に換 算 す るQ

　

命 令選 択の ア ル ゴ リズ ムを次に示 す。 隣接 命 令

，

ブロ _ッ クすべ て に対 して

Fm

＝ Km

’

ATmtdSnt を計 算する ；

do

　while （空 き制 御 記 憶 量＞o）；

　

空 き制 御 記憶量を補正 し ながら

Fm

が大 きな値を

　

もつ m か ら 順 に選 択 すべ き命 令の候補と する；

　

もし候補 と なっ た m がブロ ッ ク で か つ m に含

　

ま れ る 隣 接命 令ゴが すで に選 択 すべ _{き命 令}の候 補

　

な ら

，

再び iに対 する評 価を や りな おす ； end ； 合 成 命 令の候 補に残っ て い る隣 接 命 令

，

ブ ロ ッ クを 合 成 命 令 と して選 択する； 1

．

↑

　 　 　0

．

　 　 　0

．

0

．

　 　 　0

．

Uh

一

0

　　　 1　　 　 2 3　 　 　 4 チ ュ

ー

ニ ング回 数　 → 図 12 チ

＝一

ニ ン グ の結果 　最 終 的に ， 選択された合 成 命 令に 1バ イ トの オ ペ コ

ー

ドをあた える。 現 段階で は オペ コ

ー

ドが 1パ イ トの 固 定 長 と なっ てい る ため

，

命 令の総 数が 256 をこ えた場 合

，

本ア ル ゴ リズム は終 了するQ 　 5

・

6

．

マ イクロ

・

_プロヴ ラム_{統 合 部}

　

マ _イ ク P

・

プ ロ グ ラ ム _{統合 部}は最 終 的に選 択さ れ た命 令の た めのマ _イ クロ ・ プロ グラ ムを初期 命 令セ ッ ト のた め のマ イ ク ロ 。 プP グラ ム に 組 み 込 み

，

新 しい マ イク ロ

・

プロ _グラ ム _の ソ

ー

ス _を作る。

6

．

シ ミュ レ

ー

シ ョ ン

結果

　

以 上の ア ル ゴ リズ ムに よ り

，

シ ミ

ュ

レ

ー

シ ョ ソで得ら れ た結果を図

12

に示 す。 対象と し た プロ グラ ムは

2

次 方 程 式の 解を求め るもの で ある。 ま た

，

シ ミ

ュ

レ

ー

_タ は

，IBM

　

4341

シ ス テ ム_上に

PL11

_{を 用}い て作成されて い る。

　

こ こ では 1_回目の チ

ュー

ニ ン グに おい て

，

ル

ー

トを計 算する部 分が ブ ロ _ッ クと認められ

，

その他い くつ かの隣 接命 令が合成される。

2

回 目で は

，

い く ら かの合 成命 令 どう しも合 成 され てい る。

3

回 目の チ

ューニ

ン グで は

，

評 価関 数が 大 ぎな値を持っ た隣接命令が多 く見つ か っ た ため実行 時間比が大 き く減 少し てい る。 これは

，

命 令 合 成 の手法 （

2

）が有 効に使用された か らである。

7

．

お わ り に

　

本論文で は

，

繰り返 し実 行される同 種の問 題の動的 な 特 性 を機 械 語の_実行 履 歴とい う形でと ら え

，

これ を解 析 し個々 の命 令 列 をマ イ ク ロ ・ プロ _グラムで 1つ の 新 しい 命 令に合 成 する。 そ し て， 合成し た命 令か ら新 しい 命令 として 適 当であると 評 価 さ れ た命 令を選 択するこ と に よっ て効 率の良い チ ュ

ー

ニ ン グ を行な う方法を示 し た。 し か し

，

合 成されたマ _イク 卩

・

プロ グラ ム の最適化を行 なっ てい ない こ と

，

本 シス テムの評価が不十 分であるこ と

，

現 在

1

バ イ トの固定長で あるオペ コ

ー

ド

・

フ _ィ

ー

ル ドまた は， 命 令全 体 を 可 変 長に し た場 合に本 シ ス テ ム は どの ように変 更され

，

どの程 度の効 果が_得ら れる か を考 察するこ と

，

な どが今後の課題 として残 され てい る。 ）

1

）

2

） 3 参 考 文 献

Hockny ，

　R

．

　W

．

　and 　

Jesshope

，　C

．

　

R ．

：

“

Parallel

Computers ”，

　

Adam

　Hilger　

Ltd．

，　

Bristol

（

1981

）

．

Rauscher，

　

T ．

　

G ．

　and 　

Agrauwara ，

　

A ．

　

K ．

： Na

−

tional　

Computer

　Conference

，

　pp

。

　715

−

722（1976）

．

Aho

，

　

A ．

　

V ．

　and 　Ullman

，

　

J

．

　

D ．

：“Principles　of

相 模工業大学紀 要 第 20 巻 第 1 号 ） 4 ） ） ）

FD67

Comiler 　Design

”

_，　 Addison

−

Wesley 　Publishing

Co ．

（

1977

）

．

Abd

−

Alla，　

A ．

　M

．

　and 　Karlgaard ，　 D

．

　

C ．

：

IEEE

Trans．

　 on　

Computers

，　

Vo1．

　

C −23

，　 No

．

8，　pp

．

802−807

　（

1974

）

．

坂 村

，

相 磯 ： 電 子 通 信 学 会 論 文誌

，

Nov

．

1977

．

坂 村， 相磯， 飯 塚： 信 学 技 報

，

EC75

−

28

．

Sakamura ，　 Kり Morokuma ，　 T

．

，　Aiso，　H

．

　and

　 　Iizuka

，

　H

．

： National　

Compute

　

Conference，

　pp

。

　 　499

−

512　（1979）

．

8＞ AM 　2900　

Bipolar

　Microprocessor 　

Family，

　AMD

　 　 社

．

9_）

Ganapathi，

　M

．

，

　Fischer

，

　C

．

　N

．

　and 　Hennessy

，

　 　∫

．

L

．

，　ACM 　Computing 　

Surveys，

　

Vo1，

14

，

　

No ．