エミュレータの基本部分を固める上で最も重要な基礎の一つは、質の高いスケジューラです。
ターゲットシステムの複数のプロセッサ(CPU,GPU,APU,...etc)をエミュレートする場合、各プロセッサが他のプロセッサに対して時間的にどの位置にあるかを追跡し、適切なクロックスピードでエミュレートできるようにする方法が必要です。
これには大きく分けて2つの方法があり、どちらを選択するかは、エミュレートしようとしているシステムの複雑さによります。
前置きが長くなりましたが、この記事では、エミュレートされた各プロセッサをスレッド、特に協調スレッディングやステートマシンをベースにしたスレッドと呼んでいます。
したがって、スレッドスケジューラの実装方法については後述します。これらのスレッドは、一般的なプロセッサ、グラフィックチップ、オーディオチップなど、システム内のあらゆるコンポーネントを指します。
相対スケジューラは、速くて簡単で、うまくやれば基本的に時間の管理が完璧にできます。
最大の弱点は、2つのスレッド間で1対1の関係でしか動作しないことです。もちろん、1対1の関係をいくらでも作ることはできますが、最終的には複雑すぎてコストがかかるため、あまりいい結果にはなりません。
相対スケジューラが有効な使用例はスーパーファミコンであり、逆にひどい使用例はセガCDでしょう。
相対スケジューラを実装するには、1対1のスレッド関係ごとに符号付き64bit整数を保持する必要があります。
スーパーファミコンのレイアウトを見てみると、基本システムは、汎用プロセッサ（CPU）、オーディオコプロセッサ（SMP）、グラフィックチップセット（PPU）、オーディオジェネレータ（DSP）で構成されています。
スーファミの場合、DSPはSMPとしか直接通信できず、PPUはCPUとしか直接通信できません。そのため、以下の組み合わせに対して64bit整数が必要になります。
CPU <-> PPU
CPU <-> SMP
SMP <-> DSP
CPU <-> SMP
例えば、21,477,272hzで動作するCPUと、24,576,000hzで動作するSMPとの相対的な時間を追跡したいとします。この目的のためにint64型のcpu_smpというスケジューラ変数を用意します。
これは、相対的なタイミングのクロックを表します。電源投入時とリセット時には、このクロック変数をゼロに設定します。
cpu_smp >= 0のときはCPUがSMPよりも実行が進んでいます。逆にcpu_smp < 0のときはSMPのほうがCPUより実行が進んでいます。
CPUをNクロック実行した場合はcpu_smpからN * 24,576,000を引き、逆にSMPをNクロック実行した場合はcpu_smpにN * 21,477,272を加えます。
cpu_smpが0のときはお互いのプロセッサが、まさに同じ時間状態(同期)であることを示しています。
ここで重要なのは、CPUの実行はN * SMP_frequencyを引き、SMPの実行はN * CPU_frequencyを加える点です。
相手側の周波数の倍数だけステップすることで、相対的な時間を保っています。
CPU <-> PPU
CPUとPPUは両方ともクロックが 21,477,272Hz です。なのでSMPの場合と違って、相手の周波数をステップ掛けなくても同期をとることが可能です。
問題点
問題点として、スケジューラ変数のオーバーフロー/アンダーフローが挙げられます。特にCPU <-> SMPの場合はクロック数をかけている分、オーバーフロー/アンダーフロー問題がPPUよりも起こりやすいです。
This gives us 63-bits of usable precision in either direction, and 2^63 / 24,576,000 tells us that the CPU can advance up to 375,299,968,947 clocks ahead of the SMP before cpu_smp would underflow. That's 17,474 seconds, which seems like more than enough time to ever worry about it. But the general idea is that you would never want to allow the CPU to run more than that amount of time ahead of the SMP.
You can just slightly start to see the issue with relative scheduling by noting that whenever the CPU steps by N clocks, it needs to update both cpu_smp and cpu_ppu. The more processors you add in, the more work this becomes.
Take the Sega CD, where you have two 68K CPUs, a Z80 APU, a VDP graphics chip, a PSG audio chip, a YM2612 FM synthesis chip, a CD drive controller, a custom ASIC graphics scaler, and more ... almost all of which can directly communicate with each other, and a relative scheduler turns out to be a rather bad choice.
絶対スケジューラは、やや複雑ですが、任意の1つのスレッドの現在時刻を他の任意のスレッドに対して、つまりN:Nで検査するために使用することができます。このため、前述のセガCDなどのシステムには最適です。
ここでの考え方は、各スレッドがそれぞれ64bitの符号なし整数のタイムスタンプを保持しており、スレッドを実行する際に、そのカウンタを実行時間分インクリメントするというものです。このカウンタが他のスレッドのカウンタよりも進んでいれば、そのスレッドは時間が進んでいることになります。
もちろん、これらのカウンタもいずれはオーバーフローしますので、定期的に、すべてのスレッドのカウンタをチェックして最小の値（つまり、時間的に最も後ろにあるスレッド）を見つけ、その値をすべてのスレッドから差し引く必要があります。さらに、どのスレッドも64bitのカウンタをオーバーフローさせるほど長く実行できないようにしなければなりません。
絶対スケジューラーで問題となるのは、スーパーファミコンのように 21,477,272Hz と 24,576,000Hz のように異なる複数のクロック周波数が、ナノ秒のような一貫した時間単位に直接対応しないことです。
そのため、まずすべてのプロセッサのクロックレートをナノ秒などの時間単位に正規化する必要があります。実際の発振器も100%正確ではないので、絶対的な完全同期は必要なく、多少の端数丸め誤差は許容できます。しかし、それでもナノ秒よりははるかに良い結果が得られます。
また、前述のように、パフォーマンス上の理由から、浮動小数点ではなく、64bitの符号なし整数を使用します。
まず最初に定義しなければならないのは、64bitの範囲で表現できる時間の長さで、これは未来の最も遠いスレッドが過去の最も遠いスレッドよりも進んでいる最大の時間になります。
一般的には、1秒という時間を選択するのが良いと思います。スレッドを正規化する必要があることを検出するために、私は64bitを使用しています。つまり、カウンタが2^63に達したときは、時間的に最も遅れているスレッドを見つけて、そのカウンタをすべてのスレッドから差し引くときであることを示しています。
そこで、1秒を表す定数Secondを2^63 - 1と定義します。
1秒に収まる数字の数がわかったので、各スレッドの頻度をそれに合わせて正規化することができます。
そこで、各スレッドの定数スカラーをSecond / Frequencyと定義します。
スレッドがNクロック進むたびに，その64bit符号なしカウンタはN * (Second / Frequency)だけインクリメントされます。
1秒あたり2^63 - 1個のティックがあるとすると、attoseconds（10^18）の10倍の精度で時間を追跡できることになります。
64bitのCPUでは128bitの演算が可能であり、uint128などの型を使えば2^127の精度が得られます。もちろん、実際にはその必要はありません。
繰り返しになりますが、このバランスをどうとるかは自由です。精度を上げることで最大先読み時間（1秒以上）を長くしてもいいですし、先読み時間を長くして精度を上げてもいいでしょう。
しかし、実際には、上記の64bit整数と1秒の時間間隔は、ほぼすべてのユースケースで十分なはずです。
bsnesでは相対スケジューラを、higanでは絶対スケジューラを採用しています。
ご覧のように、後者はかなり複雑で、スーパーファミコンという単純なケースでは、相対スケジューラを使った方がパフォーマンスが高いのです。
しかし、higanは非常に多くのシステムをエミュレートしており、その多くは相対スケジューラではうまく機能しないため、代わりに絶対スケジューラを使用しています。