Linux/4004: 商用目的なしでIntel 4004上でLinuxを起動する
(dmitry.gr)- 1971年の4ビット Intel 4004のみをCPUとして使う実機ボードでDebian Linuxが起動し、古いマイクロプロセッサの限界とソフトウェア階層化の極限を示した
- Linuxは4004上で直接動作するのではなく、4004アセンブリで作られた MIPS R3000/DECstation 2100エミュレータ 上で起動し、ディスクとコンソールの一部はハイパーコールと準仮想化ドライバで単純化されている
- 4KB ROMの制約、4ビット演算、論理演算の欠如、浅いコールスタック、4002 RAMの特殊なアドレッシングのため、ROMバンキング、lookup table、status nibble、PSRAMベースの仮想RAMのような回避策が必要だった
- 最適化後、実際の4004の740KHz基準でのLinux起動予想時間は 4.76日 で、製作ボードは790KHzにオーバークロックされ、仮想MIPSは約74.73Hzで動作する
- 成果物は壁に掛けられる レトロアートボード として設計され、40x2 VFD、32個のPC LED、SDカード、SPI PSRAM、UARTを備え、ソースとディスクイメージは非商用利用条件で公開されている
実機4004でDebian Linuxを起動
- Linux/4004は、1971年のIntel 4004を唯一のCPUとして使う実機ボードで Debian Linux を起動したプロジェクトである
- 4004は世界初の商用生産マイクロプロセッサとして紹介されており、プロジェクトでは1970年代の実物のIntel 4004チップが使用されている
- デモ動画は退屈さを減らすため区間ごとに可変倍速処理されており、画面内の時計とカレンダーは正確である
- 一定倍速で再生されるオリジナルに近い性格の動画も別途提供されている
なぜ4004だったのか
- 2012年には8ビットAVRマイクロコントローラでLinuxを動かして「最低スペックでのLinux実行」記録を打ち立て、その後さらに実用的なLinuxCardプロジェクトも進められた
- 2023年にAVRベース記録の更新を狙う試みと、MOS 6510でLinuxを起動するプロジェクトが登場したことで、さらに低いレベルのCPUが目標になった
- 候補だったIntel 8080や8008よりさらに古い世代にさかのぼるため、1971年の Intel 4004 が選ばれた
- 4004は4ビットチップであるため、8ビットCPUより低い基準を明確に打ち立てられる
Intel 4004の制約
- 4004は4ビット単位で動作し、ほとんどの命令は1バイトで8クロックサイクルで実行される
- 一部の2バイト命令は16サイクル必要である
- FINは1バイト命令だが16サイクルかかる例外である
- 命令セットには AND、OR、XOR のような論理演算がなく、基本的にADDとSUBが中心である
- carry flagはSUB入力ではborrowのように、SUB後はnot borrowのように動作する特殊な方式で、実機ハードウェアで確認された
- 内部レジスタは4ビットが16個、PCは12ビット、ハードウェアreturn stackは4段である
- 現在のtop stack entryがPCとして使われるため、実際の関数ネストは最大3段である
- 割り込みはなく、TESTピンを条件分岐でポーリングする方式が外部イベント処理に最も近い
メモリとI/O構造
- 4004はメモリ命令自体を直接処理せず、バスに接続された 4001/4002/4289/4265/4308 のようなチップが命令をデコードして実行する
- 4001は256バイトのmask ROMと4ビットI/Oポートを持つROMチップで、ROM内容とI/Oポート構成は製造時に固定される
- 4002は320ビットDRAM、refresh回路、4ビットのoutput-onlyポートを持つRAMチップである
- RAM bank 1つは4個の4002で構成できる
- 各RAM bankには直接アドレス指定可能な256 nibbleと、別経路でアクセスする64個の status nibble がある
- 4289は4008と4009の機能を統合したROMコントローラで、4004を5V EEPROM/EPROMへ比較的容易に接続できるようにする
- メモリアクセスにはbank選択、アドレスをレジスタペアへロード、SRCでバスへアドレス送出、RDM/WRM実行といった多段階の手順が必要である
- status nibbleはよく使うデータへ高速にアクセスするのに有用で、MIPSエミュレータ速度を約30%引き上げるのに貢献した
開発ボードとエミュレータの準備
- 初期検証用の開発ボードは4201 clock generator、4004 CPU、4002-1 RAM、4289 ROM controller、ROM役のATMEGA48で構成された
- 電源は5Vから始め、絶縁型5V-to-10V boost converterの正極を接地して-10V電源を作り、MCS-04チップに供給した
- 最初の4004プログラムは4002 output pin 0に接続されたLEDを点滅させるコードで、電流制限を引き上げた後に動作した
- 実機ボードを作る前に u4004 という4004エミュレータを作成した
- 4004コアだけでなく、仮想SDカード、SPI UART、VFD、4002配置、PC LEDまでエミュレートする
- 実機ハードウェアではデバッグが難しいSPIピン状態や周辺機器の動作を先に検証するためのものだった
Linuxを直接動かさずMIPSをエミュレート
- Linuxは4004上で直接実行できない
- 4004向けCコンパイラがなく、アーキテクチャ上の制約からLinuxカーネルを直接載せるのは難しいと判断された
- コールネスト、ROM/RAMアドレス空間、4ビット演算の限界が直接実行を妨げる
- その代わり、4004上で MIPS R3000 エミュレータを書き、その上でDECstation 2100向けLinuxを起動する
- MIPSは他の候補より4004のコード空間内でエミュレートしやすいため選ばれた
- ARMは任意のshift operandが多い
- RISC-Vはアドレッシング方式のため遅くなると判断された
- x86は命令デコードだけでも4KBを超えうる
- PPCは複雑すぎる
- 当初の目標は、4004が基本的にアドレス指定できる 4KB ROM の中にエミュレータ全体を収めることだった
MIPSエミュレータ実装上の回避策
- MIPS命令のデコードだけでもかなりのROM空間を消費する
- 最上位opcode 64個のdispatch tableには128バイトが必要である
- 追加のsub-tableまで含めると、主要デコードだけで359バイトが必要だった
- MIPSの32個の32ビットレジスタは1024ビット、つまり4004の観点では256 nibbleであり、RAM bank 1つを占有する
- MIPS TLBは本来64 entryだが、Linuxが厳密に64個を要求しないため 16 entry に削減した
- TLB entry数は4、8、12、16個構成にもできるよう設計された
- 4004には論理演算がないため、AND/OR/XOR/NORは加算とcarry、shift、ループで実装された
- 後にはROM空間の拡大後、256-entry lookup tableで最適化された
- shiftも4004の1ビットcarry経由回転命令だけで実装しなければならず、その後nibble単位コピーと最大3回のbit shiftで改善された
- MIPSの
$zeroレジスタ処理は、4004のcircular return stack特性を利用してROM空間を節約した- 宛先が
$zeroの場合はreturnせず次の命令処理へ進む方式で、callsiteごとに3バイトと3サイクルを削減した
- 宛先が
ROMバンキングと性能改善
- 4KB ROMだけではSDカード、PSRAM、VFD、UARTなどを扱うコードまで収められないため、8KB ROM を2つのbankに分けて使用した
- ROM bank切り替えは4002 output pinで制御し、bank間call/returnのためにveneerを配置した
- ROM空間が増えた後は性能最適化が可能になった
- AND/OR/XORはそれぞれ256-entry lookup tableで実装された
- nibble乗算lookup tableを用いたことで、multiplicationは従来のbit単位実装より8倍高速になった
- 論理演算lookup tableは、4004のJINがROM page末尾にあると次のpage基準でjumpするという特性を活用している
- multiplication tableは、FINでROMのbyteデータを読む方式と0 entry処理の回避を組み合わせて実装された
最終的なハードウェア構成
- 最終ボードは1970年代風のスルーホール主体のアートボードとして設計された
- 太い直角トレース、viaなし、壁掛け用の穴、VFD表示装置を備える
- 主な構成要素は以下のとおり
- 4004 または 4040 CPU
- 4201 clock generator
- 4002 RAMチップ群
- 4289 ROM controller
- EEPROM
- SPI PSRAM 1～2個
- SDカードスロット
- SC16IS741A SPI UART
- 40x2 VFD
- 32個のPC表示LED
- SPI PSRAMは仮想MIPS RAMとして使われる
- 1つ目のPSRAMはカーネルを連続してロードする必要があるため、最低4MBが必要
- 2つ目のPSRAMは空のままにするか、128KB以上の任意サイズを搭載できる
- VFDにはFutaba M402SD10FJが使われ、Noritake CU40025-UW6Jが互換と伝えられている
- UARTは、スルーホールのSPI UART候補だったMAX3100にフロー制御上の制約があったため、SC16IS741Aの表面実装部品が選ばれた
電源とレベルシフティング
- MCS-04部品は-15V系の特殊な電圧と反転ロジックを使う
- システム全体としては-10Vと+5Vの供給と考えたほうが単純
- ボードはUSB-C edge connectorから+5Vを受け取り、+3.3Vと-10Vも生成する
- +3.3V step-down regulatorはLM2574ベースで構成される
- -10V電源は、初版のMAX764では十分な電流を供給できなかったため、MAX774と外部FET、大きなdiode、大きなinductorの構成に変更された
- 最終的に-10Vで700mA以上を供給し、rippleは200mV未満となった
- 4002 outputを3.3V domainへ変換するレベルシフティングは難しく、10K pulldown、2.7K resistor、TVS clamp、抵抗分圧を組み合わせる方式で解決された
デバッグツールと実際の不具合
- 4004には内蔵デバッグ機能がないため、Saleae LogicでMCS-04 busを長時間キャプチャした
- MCS-04 bus decoderを作成し、bus state、ROM address、ROM read value、disassembly、RAM/I/O read/write値を解析した
- その後Saleaeにコントリビュートされ、一般のSaleae softwareに取り込まれた
- revision 1.1ボードでは、出力文字がまれに化ける問題があった
- たとえば
iがhに、CがBに見えるように下位bitが消える形だった
- たとえば
- 解析の結果、kernel
memcpy()中にemulated$t1が保存されていた4002チップで、特定のnibbleの最下位bitがときどき1から0に落ちる不具合が確認された - その4002を交換したあと、テキスト出力は正常化した
ブート経路
- firmwareはまず3番目のRAM bankのメモリチップ数をprobeし、TLB entry数を把握する
- その後VFD、UART、SDカードを初期化する
- SDカードの初期化に失敗した場合は
"Failed to init SD card. Halting here and now!"を表示する - この文字列はfirmware全体で唯一の文字列である
- SDカードの初期化に失敗した場合は
- firmwareには仮想ROMを置かず、SDカードの先頭sectorをRAMの
0x80000000にロードしてからジャンプする - 先頭sectorの446バイトloaderはpartition tableからtype
0xBBpartitionを探し、0x80001000に読み込んでジャンプする - 2段目のloaderは約14KBで、Cで書かれている
- active partitionをFAT12/16/32としてmountする
vmlinuxをELFとして解析し、RAMにロードしてentrypointへジャンプする- machine type、magic value、RAM mapping、early console printing用のcallback tableを渡す
ディスクとSDカードアクセス
- ディスクアクセスにはLinuxCardプロジェクトと同じPVD準仮想化ディスクドライバを使う
- 4004 assemblyでSII SCSI chipとSCSI diskをエミュレートする代わりに、sector read/write hypercallが仮想MIPS側からDMAのように動作する
- Linux/4004ボードの総RAMは、status nibbleまで含めると440バイト、除くと352バイトしかない
- MIPS register stateとTLBがそれぞれ大きな割合を占めるため、SDカードの512バイトsector bufferを置く余地がない
- SD sectorデータは4004 RAMに保持せず、SDカードとPSRAMの別々のSPI busを使って、直接PSRAMへ読み込むかPSRAMからSDへ書き込む
- SD sector 1つの読み書きには約1秒強かかる
- SD specのACMD41初期化タイミング要件はビットバンギングSPIでは満たせなかったが、テストしたSDカードは5KHzおよび200ms以上の間隔でも初期化できた
実行速度と最適化結果
- 実際のSDカードとSPI PSRAMをエミュレートした後の初期見積もりのブート時間は、740KHzの4004基準で8.9日だった
- 主な最適化結果は以下のとおり
- 論理演算とmultiplication lookup tableで8.4日
- PSRAM nibble送受信ループの展開で7.25日
- specialized memory copyとループ展開で6.63日
- 現在の命令保存領域の削除とliveness追跡で6.50日
- shift改善で6.19日
- PSRAM address sendingループの展開で6.01日
- Linux kernel configの削減とdummy console 1x1設定、tiny initの採用で5.33日
- 2TB超のblock device対応の削除とext4
huge_filesfeatureの無効化で4.81日 - instruction fetch専用fast pathで4.76日
- 4.76日でのブートは、740KHzの4004基準で約70HzのMIPS machineに相当する
- 製作されたボードは4201をdivide-by-7モードで使い、5.5296MHz crystalを用いて790KHzにオーバークロックされている
- Linux/4004ボードの4004 instruction mixは、16-cycle命令が8.8%、8-cycle命令が91.2%で、effective speedは90,640 instructions/sである
- 仮想timer interruptは16Hzで、65,536 virtual instructionごとにIRQを送るため、仮想CPUは1.05MHzとして認識する
- 実際のemulated MIPS guestは740KHzで約70Hz、790KHzで約74.73Hzである
- 時間は14,030倍に引き伸ばされ、仮想1秒は現実の約3時間54分に相当する
Linux構成と使用体験
- Linux kernelは不要なsubsystemやfilesystem、TCP/IPなど不要な設定を削って約2.5MBまで縮小した
init=/bin/shだけを使うと、session、$PATH、/proc、/sysなどがない状態になるため、tiny initである/sbin/uMIPSinitを作成した/procと/sysをmountする- hostnameと
$PATHを設定する shが終了するたびに再実行する
- 4.5MB RAM、たとえば4MBチップ + 512KBチップだけでも、swapなしでshell promptまでブートできる
- swapを有効にすると、デバイス上でkernel sourceをビルドできる
- kernel source buildには数年かかる見込み
- ext4 journalのおかげで電源が切れても、再起動後にfilesystemを復旧してcompilationを再開する計画である
アートボードとしての目標
- このプロジェクトは最初から部分的に芸術的な目標を持っていた
- ボードは壁に掛けられるよう設計され、VFD、レトロスタイルのPCB layout、PC LEDを備える
- VFDとserial portに、Mandelbrot setをtext modeで描画するプログラムが含まれる
- 浮動小数点版
/root/mandelbrotは、Linuxが浮動小数点演算をエミュレートしなければならないため、13行 x 40列の画像を描くのに約30日かかる - 整数のみの版
/root/mandelbrot_nofpは9時間以内に完了する
- 浮動小数点版
部品コストと再現性
- 他の人が再現できるようにすることが重要な目標だったため、入手しにくい4265は避けた
- 4201は代替クロック回路よりシンプルで、4289は4008+4009の組み合わせより入手しやすいため採用された
- ボードは4004の代わりに4040も搭載できるよう設計されており、4040の追加機能は使わないため4004互換性を維持している
- TLB用の4002チップは1、2、3、4個だけ搭載して、それぞれ4、8、12、16エントリのTLBとして使える
- TLBエントリ数が少ないと性能が低下する
- 該当バンクはPC display LEDの上位16ビットも担当するため、一部だけ搭載すると一部のLEDが動作しない
- 1970年代の部品は高価
- 4004は約$250
- 4040は約$60
- 4201は約$50
- 4002-1は約$7
- 4002-2は約$25
- 4289は約$70
- 現代の部品は比較的安価で、SPI VFDは入手しにくいことがあるが、eBayで$15で入手した例がある
- VFDを搭載せず、serial portだけで対話する構成にも対応している
動画制作の過程
- 実際の起動画面は約9日間にわたって写真を撮影し、動画にした
- 1920x1080の写真を2秒ごとに撮ると1時間あたり約1.76GBが生成され、9日間の撮影では約379GB、約38万8千ファイルになる
- Android端末は長時間撮影中にハングや過熱の問題があり、iPhone SE3は撮影自体は安定していたものの、保存容量と写真のオフロードに問題があった
- 最終的に512GBのiPhone 12 Pro Maxを使って全体を連続撮影し、Linuxでifuseでmountした後、
cp -Rvfで約40万ファイルを10時間以上かけてコピーした - 最終動画はffmpegコマンド群で作成され、退屈な区間は可変倍速で処理された
- 再生速度は5FPS、つまり10x realtimeから、960FPS、つまり1920x realtimeまで変化する
- 別途無編集版は0.5FPS capture、60FPS playbackで、120x realtimeの速度になっている
公開資料とライセンス
- SDカード用のdisk imageは別ダウンロードで提供される
- main downloadには次が含まれる
- Saleae software用のMCS-04 bus analyzer
- i4004 DECstation 2100 emulator source
- MIPS MBRとsecond-stage bootloader source
- kernel configとversion info
- Linux/4004ボード用u4004 emulator source
- ライセンスは非商用利用は無料で、商用利用には別途ライセンスが必要
- どのような利用であっても、sourceとbinary formで元の作者をcreditする必要がある
2件のコメント
元記事の著者は、今回DEF CONでバッジ絡みの件でステージから連れ出されたあの人なんですね。どちらの肩を持つつもりもありませんが、それでも実力は本当にすごいですね。
Hacker News のコメント
うわ、15MHz の m68030、16ビットメモリバス、RAM 10MB で現代の NetBSD は遅いと思っていたけど、これは本当に狂っている。
80年代末〜90年代初頭に、コンピュータが永続ストレージ、開かれたアドレス空間、MMU を備え始めたことで、実質的に現代のコンピューティングに到達したことがよく分かる。
Amiga 3000 や i80486 のコンピュータでも現代のコンピュータと同じものを実行できるし、今はずっと速く実行できたり当時はなかった GPU のようなものもあったりするが、機能的には大きな違いはない。
Dmitry が 機能的 という言葉をどれほど緩く定義できるかを見せてくれるのが良い。
実際の郵便で手をやり取りし、1局に何か月も何年もかかることもあった。
返事が来るころには元の戦略を忘れてしまうこともあり、チェスに別の難しさが加わっていたのだが、このプロジェクトは実質的に 通信 Linux だ。
コマンドの出力が返ってくるころには、なぜそのコマンドを実行したのか忘れてしまうかもしれない。
80年代末〜90年代初頭どころか、実は1960年代末ごろにはすでに可能だった。
Linux を IBM Model 67 [1] に移植することも可能そうだし、GCC はすでにその命令セットをターゲットにできるので簡単かもしれない。
MMU も十分で、高速なコアメモリが最大 2MB という制約は厳しいが、その 68030 マシンと同程度で少し遅いくらいだろう。
完全仮想化や、ハードウェアが強制するメモリ・入出力境界も初期に発明されていたが、こうした機能がミニコンピュータやマイクロコンピュータに降りてくるまでには時間がかかり、一般的なソフトウェアが活用するようになるまではさらにずっと長くかかった。
[1] https://en.wikipedia.org/wiki/IBM_System/360_Model_67
どんなチューリング完全なシステムでも何でも実行できるし、非常に遅いことはあっても実行はできる。
時間さえあれば ChatGPT も 4004 上で動かせる。
車輪に自動車を取り付けると、車輪がさらに3つ増えるようなものだ。
Hackaday Supercon 2002 の参加者バッジ（https://hackaday.com/2022/10/12/the-2022-supercon-badge-is-a...) は、仮想の 4ビット CPU と、命令を直接入力して実行・ステップ実行できる制御パネルを実装していた。
制御パネルにはメモリ1ページをビット単位で見られる画面があり、その上に宇宙シューティングゲームを実装するのが本当に楽しかった。
Voya4 アーキテクチャを 4004 と比較するのも興味深く、似たようなトレードオフもあったが、Voya4 には50年分の CPU 命令セットの経験という利点がある。
ただし dimitygr のやり方はそのバッジでは通用しない。CPU エミュレータを実装している PIC24 の中にメモリと RAM がすべて内蔵されているからだ。
参考までに、4ビット CPU は今でも作られ使われている。大量生産されている多くの赤外線リモコンは 4ビット MCU でプログラムされている。データシートは https://www.emmicroelectronic.com/sites/default/files/produc... を見るとよい。
性能不足のマシンで何かを動かせるかと聞かれたとき、AVR の例 をよく挙げていたが、これで新しくリンクできる例ができた。
周波数と消費電力を見ると、どれくらい RF をまき散らしているのか、SDR のウォーターフォールで検出してデコードできるのかも気になる。
まだ読んでいる途中だが、現時点では「soubroutine」という単語が見えていて、タイプミスのようだ。
うわ、これは安く済んだプロジェクトではなかっただろう。eBay のコレクターたちのおかげだ。
そしておそらく、私が VFD ではなく LCD を選んだ唯一の状況だったと思う。
数年がかりのコンパイルを走らせるなら、終わるころには VFD は焼き付きで大変なことになっていそうだ。
残念ながら、大学の教職員は HN をあまり読んでいないようだ。
うわ、すごい。
高位の PC ビットを見ると、今何が実行中なのか分かる。
追伸: それでも、インターネット越しのサーバーのひどい IPMI で仮想 ISO からカーネルをロードするよりは速い ;D
vmlinuxにnmをかければ、カーネル関数 と簡単に対応付けられる。ユーザー空間に入った後は、メインバイナリ（0x01000000 よりかなり下）と共有ライブラリ（0x77000000 付近の高いアドレスにロードされる）も区別できる。
起動も実行も苦痛なほど遅かった。
本当に興味深い記事だった。
4004 について少し読んで、変なチップだとは知っていたが、難解さの度合い が想像を超えている。
今なら同じトランジスタ数で CPU を作るとどれくらいうまく作れるのか見てみたくなった。
6502 よりそれほど大幅に少ない数ではないし、8ビットならプログラミングはずっと楽になりそうだ。
動画の撮影に9日かかり、エミュレーション1秒あたり4時間 かかった。
それに、なぜ Windows 95 を使っているのかも気になる。
動画用に、USB ではない実シリアルポート付きのノート PC が必要だった。
このノート PC が条件に合っていて、eBay で20ドルだった。
個人的に Windows 2000 がいちばん見た目の良い Windows なので、デモ動画用にインストールした。
本当にすごい
このプロジェクトの大部分を理解できるくらい知識が増えていたらよかったのだが、今の自分の限られたコンピュータサイエンスの力では難しすぎた
それでも完全に理解できたハイライトは「Section 14.b & 14.c - Getting the data...」だった
たった40万個のファイル、4年間にわたって1日約275枚の写真があれば十分だった
処理・ストレージ・ネットワーク性能がこれほど有り余っているのに、最もよく使われていそうなメディア同期アプリがフリーズしたり同期が遅かったりし、AirDropは失敗し、「すべて選択」というUI機能すらない時代だなんて、本当に奇妙な時代に生きている :)
こういうものにはノーベル賞のようなものが必要だ
コンピュータサイエンスの奇妙で特異な応用を評価する部門を追加してもよさそうだ
「Why MIPS?」セクションで「一部はひどいアドレッシング方式のせいで遅くならざるを得ない（RISCV）」とあったが、RISC-Vのアドレッシング方式の何が問題なのか？
RISC-Vの一部の命令では、即値ビットが連続して格納されていない
MIPS命令では、即値加算、定数ロード、分岐などの値ビットは常に順番どおりに格納される
RISC-Vではビットがときどき入り混じっている
例えば無条件分岐では、宛先オフセットのビットが bit 19, bits 9-0, bit 10, bits 18-11 の順に格納される
ハードウェアでは配線を正しく接続するだけでよいので並べ替えのコストは事実上ないが、ソフトウェアではこれを直すために多くのビット操作が必要になる
RISC-Vがこうしている理由は、ハードウェア設計を単純化するためだ