バロース B5000
バロース B5000は、バロースが1961年にリリースした大型コンピュータの名称。当時バロースは、大型・中型・小型でそれぞれ全く異なるアーキテクチャを採用し、のコンセプトからそれぞれ命令セットを特定の高水準言語向けに最適化するという戦略をとった。大型システムの設計部門はスタックマシン型命令セットを採用し、命令の密度を高めると共にデータワード長を48ビットとした。B5000は ALGOL 60 向けに最適化されており、単純なコンパイラでコンパイル可能とした。後継にはB5500がある。その後、B6500/B6700 やその後継機がリリースされた。なお、中型システムはCOBOLに最適化されており、小型システムはコントロールストアが書き換え可能で命令セットを置換可能とされた。
1880年代に創業したバロースはコンピュータ業界では最古参だったが、1950年代末の同社の主力製品はまだ電気機械式の Sensimatic などだった。IBM、NCR、UNIVACといったライバル企業は既に大型コンピュータを生産し始めていた。遅れて参入することになったバロースは、当時の最新のアイデアに基づく全く新たな設計を採用するという戦略をとった。B5000のアーキテクチャは長続きしなかったが、それをベースとしてB6500が生まれている。そのアーキテクチャはユニシスの ClearPath Libra ファミリに受け継がれており、B6700からサポートしているというオペレーティングシステムがほぼそのまま動作している。第三の大型システムであるB8500は商業的には成功しなかった。
最初のB5000は率いるチームが設計した。先進的なマシンとして知られている。
コンピュータアーキテクトとして知られる は最も素晴らしいアーキテクチャの1つに B5000 を挙げ、「私が見た中でも最も革新的なハードウェア/ソフトウェアの結合された例であり、当時としては極めて先進的だった」としている。後継としてB5500やB5700がある。その後、直接の後継は存在しないが、B6500はB5000シリーズから大きな影響を受けている。またオペレーティングシステムの (MCP) がB5000シリーズから移植されている。以下の議論において、B5000、Aシリーズ、およびClearPath/MCPは区別なく使われる。
B5000は、ソフトウェアのニーズを考慮してアーキテクチャと命令セットが設計されたという点で、当時としては革新的であった。当時、プロセッサとその命令セットは設計が完了してからソフトウェア開発者に渡されるのが通例であった。
B5000は高級言語をサポートするよう設計された。当時、FORTRANとCOBOLが登場したばかりである。FORTRANもCOBOLもソフトウェア技術から見れば不足である。したがってもっと新しい、まだ試されていないALGOL-60が採用された。正確にはALGOLから派生した言語 Elliott ALGOL が採用された。これはアントニー・ホーアが Elliott 503 というマシン用に開発したものである。ALGOLに現実的な入出力命令を追加したもので、強力な文字列操作機能を持っている。ホーアのチューリング賞受賞講演では、これについて論じている。
ALGOL-60は、FORTRANなど他の言語を設計した経験のある専門家たちが設計した。設計にはバッカス・ナウア記法を用い、非常にきれいな文法を持つ言語となっている。多くの言語の先祖でもあり、Pascal、C言語、Simula、Ada、Eiffelなどがそれにあたる。
B5000はしたがって非常に強力な言語に基づいている。他のベンダーはALGOLコンパイラの実装を試みたが、実装できなかったという。しかし、当時学生だったドナルド・クヌースは、夏休み期間中にバロースの以前のマシン上に ALGOL-58 を実装した。ALGOLなどの高級言語はアセンブリ言語と同等の能力がないと思われがちで、ALGOLのシステム記述言語としての潜在能力に気づいていなかった。この風潮はC言語が開発されるまで続いた。
バロースのALGOLコンパイラは非常に高速であった。エドガー・ダイクストラはパサデナのB5000の工場で自身の書いたプログラムのコンパイルを行い、その高速さに驚き、即座に何台か大学（アイントホーフェン工科大学）に欲しいと言ったとされる。このコンパイラの高速性にはいくつか理由があるが、最も大きな理由はだったためである。初期のコンピュータはメモリ容量が小さく、ソースコードをメモリ上に全て置くのも難しかった。そのためソースコードをメモリ上に保持せず、何度か読み込む必要があった。バロースのALGOLでは、各変数を使用する前に宣言する必要があった。これにより、ソースコードを1度読み込んだだけでコンパイルを完了させることができた。この概念は理論的にも深い意味があるが、同時にそれによってコンパイルが非常に高速化される。パンチカードからソースコードを読み込むと即座にコンパイルでき、バロースのカードリーダーは業界でも最速だった。
COBOLコンパイラもワンパスコンパイラで、同様に高速だった。パンチカード4000枚のCOBOLプログラムを毎秒1000枚のカードを読み込んでコンパイルできた。全ソースコードを読み込むと、即座にコンパイル済みのプログラムを実行可能だった。
B6500とB7500は、バロースのシステムとしては唯一、今日までアーキテクチャが存続している。B5000がベースとなっているが、アーキテクチャは刷新されている。主な違いは次の通り。
B8500は、B5000をベースとして開発された軍用コンピュータD825から生まれた。
B8500は、1960年代にB5500とD825の設計を統合しようとして設計された。集積回路と磁気薄膜メモリを採用している。ワード長は48ビット、スタックマシンであり、B5500のような識別子を採用しているが、互換性はなかった。またハードウェアの信頼性が低く、完全なシステムが納入されたという実績もなく、1970年以降にプロジェクトが中止となった。
バロース初の大型システムはB5000である。1961年に設計されトランジスタで構成された第2世代コンピュータであり、磁気コアメモリを主記憶に使用している。その後は B5500、B6500、B5700、 B6700、B7700、B6800、B7800、バロースAシリーズと、アーキテクチャをほぼそのまま保持しつつ、25年にわたって新たな技術で実装してきた。スペリーがバロースを買収してユニシスになっても、CMOSのASICである MCP を使った新機種を投入。2005年に発表された ClearPath Libra 590 は、MCP CMOS プロセッサと同時に Intel Xeon プロセッサを搭載でき、エミュレーションでもバロース大型システムを実行可能となっている。
B5000のアーキテクチャはALGOLスタックアーキテクチャである。これ（のメモリレイアウトとプログラムからの使い方）は、PDP-11やMC68000などのリニアなアーキテクチャとも、x86などのセグメント方式のアーキテクチャとも異なる。
ALGOLはシステム記述言語であり、B5000はALGOLを意識して設計された。これが出発点である。他のCOBOLなどの言語もサポートされた。強力な文字列操作命令により、高速なコンパイラの開発が可能となったのである。
B5000上のALGOLは拡張版であり、強力な文字列操作命令を持っているが、ALGOL本来の一部の要素（特に仮引数の型指定が不要という点）が排除されている。また、C言語の #define よりも整然としたDEFINE機構を持っており、プリプロセッサというよりも言語仕様に組み込まれていた。また、EVENT というデータ型が追加されており、プロセス間通信に使われた。また ON FAULT ブロックでプログラムの障害を扱うことができた。
ユーザーレベルのALGOLにはオペレーティングシステム (OS) が必要とするような危険な機能は提供されていない。そのために2つのレベルの言語拡張が用意されている。ESPOLとNEWPはOSおよびOSに密接に関連するソフトウェアの記述用、DCALGOLとDMALGOLはより特殊なシステムソフトウェア用である。
本来、B5000のOSであるMCPはALGOLを拡張したESPOL(Executive Systems Programming Oriented Language)という言語で記述されていた。これは70年代後半にNEWPという言語に置き換えられた。NEWPの名称の由来は不明だが、一説には"No Executive Washroom Privileges"ではないかといわれている。NEWPもALGOLの拡張だが、ESPOLよりもセキュリティを強化している。危険のある構文要素はそれを使用するブロックに明示的に使用することを示さない限り使うことができない。これによって複数レベルの保護機構を提供する。
NEWPでは、危険な構文要素を持つプログラムは実行できない。システムのセキュリティ管理者がそのようなプログラムを実行可能に設定することができるが、他のユーザーは（どれだけ特権レベルが高くても）その設定を自分で行うことはできない。NEWPは汎用のプログラミング言語だが、ALGOLの持つ機能全てをサポートしているわけではない。
NEWPにはALGOLにない制御機能もある。例えばINLINEプロシージャがある。いわゆるインライン展開を可能にするもので、論理的にはプロシージャだが実際には呼び出し側のコード内に直に展開されてコンパイルされる。これにより、プログラムの可読性とコードの効率を両立させている。
NEWPには大規模なソフトウェアの開発を可能とする機能がある。具体的にはコードのモジュール性を高める機能で、インタフェース（関数とデータの組）、インタフェースのグループ、モジュール、スーパーモジュールといったものがある。いずれも基本的には関数とデータをまとめるものであり、ある広域データのスコープを限定するものと言える。インタフェースはモジュール間のインポート/エクスポートを可能とする。
NEWPで書かれたOSとALGOLで書かれたユーザープログラムの中間に位置するものとしてミドルウェアがある。ミドルウェアはDCALGOL (data comms ALGOL) で記述される。これはOSおよびプロセス間のメッセージ交換に使われる。例えばCOMSというミドルウェアはネットワークからメッセージを受け取り、それを特定のプロセスやMCS（メッセージ制御システム）にディスパッチする。
MCSは複数のユーザーセッションを単一のMCSスタックで制御する。負荷バランス制御もMCSレベルで行われる。例えば、ひとつのスタックで30ユーザーまで管理するとした場合、ユーザーセッションが増えたらスタックを増やすことで対応する。このため、B5000では普通ならセッション毎にプロセスを生成するところをひとつのスタックで複数セッションを制御するため、性能的に有利である。MCSは大規模トランザクション処理の根幹も担っている。
MCSは外部コプロセッサ TCP (Terminal Control Processor) とやりとりする。これは24ビットのミニコンピュータで、一般的なレジスタ・アーキテクチャであり、数千の端末を制御する入出力機能を有する。TCPとB6500はメモリ内のメッセージでやりとりし、それは今日のパケットと基本的には同じである。MCSはB6500側でそれらメッセージの処理を受け持っている。TCPにはアセンブラがあるが、そのアセンブラはB6500のALGOLコンパイラに対応していた。TCPの命令ごとに対応するALGOL関数があり、そういった関数を呼び出すと、TCPに対応する命令が発行される。TCPのプログラムは、そういった関数の呼び出しが並んでいるだけのALGOLプログラムであり、アセンブリ言語のプログラムと1対1に対応している。ここではALGOLはマクロアセンブラのように機能する。まず、ALGOLで書かれたTCPプログラムをコンパイルするとB6500上の実行ファイルが生成され、それをB6500上で実行するとTCP用のバイナリがTCPに向かって渡される。
DMALGOL (Data Management ALGOL) は、DMSII データベース向けに拡張されたALGOLである。DMALGOLはDASDLコンパイラで生成されたデータベース記述ファイルからDMSIIデータベースソフトウェアをコンパイルする言語であり、データベースを利用する側は普通のALGOLやCOBOLを使うことができる。DMALGOLの最大の機能は、テーブルやインデックスを操作するコードを生成するプリプロセッシング機構である。
DMALGOLのプリプロセッシングは変数やループを含み、コンパイル時の変数に基づいて名前を生成できる。これによりループのないプリプロセッシングより遥かに調整が容易である。
DMALGOLは DMSII データベースのためのアクセスルーチンを提供するのに使われる。DASDL (Data Access and Structure Definition Language) でデータベースを定義した後、そのスキーマをプリプロセッサで翻訳し、DMALGOLのアクセスルーチンが生成され、それをコンパイルする。したがって、他のDBMS実装とは異なり、実行時のデータベース固有の if/then/else の判断が不要となる。1970年代、この最適化はメモリ使用量と実行時間の削減に大いに威力を発揮した。その後、低レベルなメモリと速度のチューニングがあまり重要ではなくなってきたことと、プリプロセッシングを廃することでコードが単純化されより重要な最適化が可能になることから、このような技法は徐々に廃れた。
後にコンパイラのコードサイズがあまり問題にならなくなってくると、プリプロセッシングの構文要素の多くがユーザーレベルのALGOLの一部に編入された。DMALGOLに残されたのは、ユーザーレベルでは安全でないと考えられる要素と、データベース記述ファイルの直接処理機能だけとなった。
初期のシステムや言語では、小さなルーチンは敬遠された。サブルーチン呼び出しと復帰は時間のかかる処理であり、コールスタックを管理するには多くの命令を実行しなければならなかった。B5000はスタックマシンであり、配列（文字列やオブジェクトを含む）以外のデータは全てスタック上にある。このため、スタック操作は効率を重視して最適化されている。スタック指向マシンであるため、ユーザーがアクセスできるレジスタは存在しない。
マルチタスクもB5000では効率化されている。コンテキストスイッチは MVST (move stack) というひとつの命令で実行できる。各スタックがプロセス（タスクまたはスレッド）に対応しており、各タスクは待っているリソース上でブロックされる。実行されるのを待っているタスクはプロセッサというリソース上でブロックする。MVSTはユーザープログラムからは実行できない。
スタック・アーキテクチャがレジスタに基づくアーキテクチャよりも遅いと信じる人もいる。性能を向上させるには可能な限りデータをプロセッサの近くに置く必要がある。B5000では、スタックの先頭2ワードをレジスタ（レジスタAとB）にしている。ほとんどの命令はこのスタック先頭2ワードを使って行われる。
性能をさらに向上させるには、スタック上のレジスタ化する部分を増やせばよい。スタックアーキテクチャの利点は、そのような性能向上策を施してもソフトウェアを全く変更する必要がない点である。レジスタをプログラムが意識するアーキテクチャでは、レジスタ数が増えれば再コンパイルなどが必要となる。
また、CPUのシングルチップ化が困難ではないかという指摘もあった。しかし、現にB5000の後継マシンはシングルチップのCPUになっている。
プログラムがスタックアーキテクチャにマッピングされる例を以下に示す。
スタックフレームは現に実行中の環境の語彙レベル (lexical level) に対応している。例でわかる通り、語彙レベルとはプログラムの静的な入れ子構造であって、動的な呼び出しの入れ子ではない。ALGOLでは、現在実行中の位置より前に宣言された変数だけが参照可能というのが基本である。また、入れ子の内部で外側と同じ名前の変数を宣言すると、外側の変数を参照できなくなる。
語彙の入れ子は静的なので、5レベル以上の入れ子構造のプログラムは非常に珍しいし、そのようなプログラムは構造化不足と言える。B5000は最大32レベルの入れ子まで可能である。
プロシージャの実行には4種類の方法 normal、call、process、run がある。以上のようにバロースの拡張したALGOLには後のAdaなどの言語に見られるマルチプロセッシング機構と同期機構が全て備わっている。また、非同期処理サポートはハードウェアレベルで行われる。
他の可能性としてプロシージャがINLINEを宣言された場合がある。この場合コンパイラはそのプロシージャを呼び出しているプロシージャ内に展開し、プロシージャ呼び出しのオーバヘッドをなくす。
例で示したプログラムは normal 呼び出しである。したがって情報は全てひとつのスタック上に配置される。非同期呼び出しの場合、スタックは複数に分割され、各プロセスは独立して動作しつつ両者のデータを共有できるようになっている。
スタックハードウェアの最適化として D (Display) レジスタがある。Dレジスタは各スタックフレームの開始地点を指す。Dレジスタ群はプロシージャ呼び出しに応じて自動的に更新され、ソフトウェアからはアクセスできない。32本のDレジスタがあり、語彙の入れ子の最大が32レベルとなっているのはここから来ている。
語彙レベル5(D[5])から語彙レベル2(D[2])の広域変数にアクセスする方法を考えてみよう。アクセスしたい変数が語彙レベル2のベースから6ワードの位置にあるとする。このアドレスは(2, 6)で表される。Dレジスタがない場合、D[5]フレームの最初にある制御ワードを見なければならない。それ(制御ワード)はひとつ前のフレームすなわちD[4]環境を含むフレームを指している。このようにフレームを逆に辿っていって目的の語彙レベルのフレームに到達する。これはプロシージャから制御を戻すときの経路とは異なることに注意が必要である。アーキテクチャ上データスタックもコールスタックも同じ構造になっているが、制御ワードによってそれらを見分けている。
これは変数へのアクセス方法としては非常に非効率的である。Dレジスタを使用すると、D[2]レジスタは語彙レベル2の環境のベースを指している。したがってある変数のアドレスを得るには、その変数を含む語彙レベルに対応するDレジスタの中身(ベースアドレス)にオフセットを加算すればよい。フレームのリンクを辿るLLLUという命令もあるが、Dレジスタを使用した方が高速である。Dレジスタを使用すれば外側のグローバルな環境にあるものにもローカル変数と同様にアクセスすることができる。
コルーチンやプロセスとして p を呼び出した場合、D[3]環境は別のD[3]をベースとするスタックとなる。この場合、別のプロセスがD[2]環境にアクセスし続けることが暗示されている。この考え方を推し進めていけば、全く別のプログラムからプロシージャを呼び出し、D[3]のスタックフレームが別のプロセスのD[2]環境を指すということも考えられる。この場合、本来のD[2]環境を直接参照することができなくなり、他のプロセスのD[2]環境を直接参照可能となる。実際、ライブラリ呼び出しはこのように実装されている。このようなスタック間呼び出しでは、呼び出し側と呼び出される側は別のプログラミング言語で書かれていても構わない。
現在のプロセスのスタックには、D[1]とD[0]環境は存在しない。D[1]環境はコードセグメント辞書であり、同じコードを実行するプロセス間で共有される。D[0]環境はオペレーティングシステムによってエクスポートされたものを表している。
スタックフレームは実のところプロセスのスタック上に存在する必要はない。この機能は初期のファイル入出力の最適化で使用された。FIB(File Information Block)は入出力処理の間、D[1]でリンクされる。90年代初め、これは言語の機能として STRUCTURE BLOCK として実装され、ライブラリ技術と組み合わせて CONNECTION BLOCK と呼ばれた。データ構造をDレジスタのアドレス範囲にリンクする機能によってオブジェクト指向が実装される。B5000はオブジェクト指向という言葉が使われるずっと以前から、その機能を使っていたのである。
スタック構造の利点として、プログラムが異常終了するときにスタックのダンプを取れば、状態が完全に把握できるのでプログラマは問題を正確に見つけ出すことができる点が挙げられる。
また、スタックアーキテクチャでは、プログラムは必然的に再帰可能となる。FORTRANは再帰不可能な言語であり、当時の人々がALGOLの実装に苦労した点は「再帰」をどう実装したらよいかという点だった。B5000では問題は全く逆で、再帰しないはずのプログラムを再帰させないようにするにはどうしたらよいかに頭を悩ませた。結局機能を限定することに時間を費やすのは無駄なので、バロースのFORTRANコンパイラは再帰可能なままとなっている。
結果として、バロースのFORTRANの実装は高く評価されている。例えば、サブルーチンや関数呼び出しで引数の個数が合っているかを（ALGOLと同様に）チェックできる。他のシステムではそのような間違いはクラッシュを引き起こした。バロースはオブジェクト指向言語Simulaなど、他の言語の実装でも優れていることで知られていた。APLの設計者ケネス・アイバーソンはバロースのAPL実装が最高であると宣言した。LISPを設計したジョン・マッカーシーは、LISP本来の能力である自己書き換えができないという点でB5000に不満を持っていた。ただし、LISPは多くの場合インタプリタとして動作する。
スタックアーキテクチャであってもプロセスが使用するメモリ量は他のアーキテクチャと同程度である。当時他のシステムでタスクを実行するに当たって必須であったメモリ割り当ての事前設定 (SYSGEN) はB5000では不要である。実際、B5000では新たな周辺機器を追加する場合も再コンパイルなどが不要だった。
多くの人にとってB5000は上述の通りスタックマシンとして記憶されている。しかし、アーキテクチャ上重要な点として他にタグベースである点と記述子ベースである点がある。
当初のB5000では、各ワードにビットが付属していて、そのワードがコードなのかデータなのかを示していた。これはセキュリティ機構の一種であり、コードの破壊(ハッカーによる不正な書き換えなど)を防ぐ。
コードを書き換えることができないため、B5000では完全なリエントラント性を備えることができる。あるプログラムを何人のユーザーが実行していてもメモリ上にはそのプログラムのコードはひとつしか存在しない。これによってメモリ利用効率が向上する。
後にB6500でこの機能が強化され、48ビットワードに3ビットのタグが付属するように実装された。内部的なデータビットはワードの0番～47番のビットであり、タグは48～50番である。ビット48はリードオンリービットである。つまりタグの値が奇数であればユーザーレベルのプログラムはそのワードに書き込むことができない。コードに使用されるタグは3となっている。以下にタグの値とその機能を列挙する:
偶数のタグの付いたワードはユーザーデータであり、ユーザープログラムが更新できる。奇数のタグの付いたワードはハードウェアが生成し、プログラムの実行状態を示している。これらのワードは特定の命令やハードウェアが生成し使用するので、そのワードの内容はハードウェアの実装によって変化するが、ユーザープログラムにはその変化は全く影響しない。
タグ1のワードはスタック上のデータアドレスを表している。IRWは現在のスタック上のアドレスを指している。SIRWはスタックを識別する番号を含んでいて、任意のスタック上のデータを参照する。
タグ5のついたワードは記述子である。タグ5のワードはスタック以外のデータのアドレスを含んでいる。
タグ7はプロシージャのエントリポイントを記述するプログラム制御ワード(PCW)である。
タグ3はコードワード自体を表す場合は、スタック上には現われない。ただし、タグ3は MSCW、RCW、TOSCWなどのスタック制御ワードとしても使われていて、これらはスタック上に存在する。
B5000シリーズは高速なバスで相互接続されたマルチプロセッサにおいても先駆的役割を果たした。B7000シリーズは最大8プロセッサであった。マルチプロセッサに関する操作としては、以下のようなものがある:RDLKは非常に低レベルなプロセッサ間同期の方法である。ユーザープログラムで使用するのはEVENTデータ型である。
Forth言語の設計者であるチャールズ・ムーアはMITでB5500に触れ、そのスタックアーキテクチャに影響された。"Forth - The Early Years"の中でムーアはForthのDUP, DROP, SWAPといったワードはB5500の命令 (DUPL, DLET, EXCH) に対応していると述べている。
ソビエト連邦のメインフレームおよびスーパーコンピュータ シリーズはB5000の影響を受けており、スタックアーキテクチャでタグ付きメモリを採用していた。一種のアセンブリ言語 El-76 を備えていたが、これが実際には ALGOL-60 の修正版であった。なお、その後 Elbrus はEPICアーキテクチャ風のVLIW型CPUに移行している。
ヒューレット・パッカード社にはバロースの元従業員だった技術者がいて、HP 3000 システムはB5000の影響を受けている。ボブ・バートンの逆ポーランド記法 (RPN) に関する業績はHPのプログラム電卓に採用され、例えば HP-35 などが有名である。
タンデムコンピューターズが1970年代末から1980年代初めにかけて設計した NonStop システムは16ビットのスタックマシンであり、HP 3000 の影響を受けているため、間接的にB5000の影響を受けている。1990年ごろMIPSアーキテクチャに移行したが、従来のスタックマシン用バイナリをエミュレーションでサポートし続けた。2000年以降、Itaniumに移行したが、そこでもスタックマシンのエミュレーションを継続サポートしている。
ボブ・バートンはアラン・ケイにも影響を与えた。アラン・ケイは B5000 のデータ駆動型タグ付きアーキテクチャに影響され、オブジェクト指向プログラミングや Smalltalk に関する考察に至った。