この内容は「Ruby 3 オブジェクト指向とはじめての設計」で取り上げた、動的回路シミュレータの最終形の1解答例です。ページの関係で、あふれてしまったので、ここに公開します。
入力の全パターンを与えて、素子の遅延時間を測定することが目的でしたが、本書の中で解説したプログラムでは、オブザーバパターンを用いているため、出力が変化しないとテスタが呼び出されず、遅延時間の測定ができない問題がありました。
これを解決するには2つの方法が考えられます。1つ目は、入力パターンが変わるごとに全てのデバイスを作り直すという方法、もう1つは、状態をリセットする手段を用意して、全端子の状態をnilに戻せるようにする方法です。
全てのデバイスを作り直すという方法は、若干オーバーヘッドがありますが、悪い方法ではありません。毎回オブジェクトが新規に生成されるので、確実に状態を初期状態に戻すことができます。今回はデバイスを引数に渡してやれば、そのデバイスに全ての入力パターンを与えるメソッドを、Simulatorに作成することを予定しています。全てのデバイスを作り直すのだとすると、回路の組み立て処理を何らかの形で、このメソッドに渡さなければなりません(おそらくはブロックで渡すことになるでしょう)。これは呼び出す側にとっては、面倒です。そこで今回は後者の方法をとることにします。
全Terminalの状態をnilにリセットする機能を作成することにします。まずSimulatorで、生成した全てのデバイスを管理できるようにします。そのために、
class Simulator def initialize @current_time = 0 @command_list = SortedList.new @device_list = [] end ... def reset @current_time = 0 @device_list.each{|d| d.reset} end def register_device(device) @device_list %lt;%lt; device end ...
次に、LogicDeviceのinitializeメソッドで、引数として渡されたSimulatorのregisterDeviceメソッドを呼び出し、その時に、自分自身を渡すようにします。そしてLogicDeviceにresetメソッドを追加します。これは、自分自身の入力、出力端子の全てのresetメソッドを呼び出します。
class LogicDevice def initialize(input_count, output_count, simulator) @input_count = input_count @output_count = output_count @input_terminals = Array.new(input_count) {|i| Terminal.new} @output_terminals = Array.new(output_count) {|i| Terminal.new} @simulator = simulator simulator.registerDevice(self) end ... def reset @input_terminals.each {|t| t.reset} @output_terminals.each {|t| t.reset} end
最後に、Terminalにresetというメソッドを追加すれば完了です。
Terminalにresetメソッドを追加してください。これは、Terminalの状態をnilに設定します。ただ、この時にオブザーバが呼び出されないように注意してください。
class Terminal ... def reset @current_state = nil end end
Simulatorのresetメソッドを呼び出せば、全端末の状態をnilにリセットすることができるようになりました。それでは、Simulatorに、デバイスのテストを行うメソッドを追加することにしましょう。本書の前章の、練習問題2-(2)を参考にして、与えられた入力数の全入力パターンを生成するpermutationメソッドを作成し、CircuitSimulatorモジュールに追加します。
def self.permutation(input_digits, input = [], &proc) end
モジュールはインスタンス生成できませんから、特異メソッドにする必要があります。各入力パターンは、配列として生成され、生成された配列は、procに渡されます。例えば、
CircuitSimulator.permutation(2) do |input_pattern| puts("#{input_pattern}") end
を実行すると、以下のように表示されるものとします。
[0, 0] [0, 1] [1, 0] [1, 1]
module CircuitSimulator ... def self.permutation(input_digits, input = [], &proc) if input_digits == input.length proc.call(input) else permutation(input_digits, input + [0], &proc) permutation(input_digits, input + [1], &proc) end end end
このようにモジュールには、クラスだけではなく、メソッドを追加することもできます。これはモジュール名.メソッド名で呼び出すことが可能です。それでは、これを利用して、Simulatorに、test_circuitメソッドを追加しましょう。これは、与えられたデバイスの全入力パターンをデバイスに与えて、遅延時間を表示するメソッドです。
与えられたデバイスの全入力パターンをデバイスに与えて、遅延時間を表示するメソッドtest_circuitを、Simulatorに追加してください。まず与えられたデバイスの出力端子全てにテスタをつなぎます。そして入力端子に対して、全ての入力パターンを生成してデバイスに与えます。
def test_circuit(device) device.output_count.times do |i| device.get_output_terminal(i).connect_input(create_tester("out#{i}")) end ここを考えてください。 end
module CircuitSimulator class Simulator ... def test_circuit(device) device.output_count.times do |i| device.get_output_terminal(i).connect_input(create_tester("out#{i}")) end CircuitSimulator.permutation(device.input_count) do |input| reset puts("#{input}") device.input_count.times do |i| device.get_input_terminal(i).state = input[i] end start end end end ... end
それでは、遅延時間を測定してみましょう。まずは半加算器です。
require 'composite_simulator' sim = CircuitSimulator::Simulator.new sim.test_circuit(HalfAdder.new(sim)) [0, 0] out1: 0 at 10ns. out0: 0 at 10ns. [0, 1] out1: 0 at 10ns. out0: 1 at 10ns. out0: 0 at 10ns. [1, 0] out1: 0 at 10ns. out0: 1 at 10ns. [1, 1] out1: 1 at 10ns. out0: 0 at 10ns. out0: 1 at 10ns. out1: 0 at 10ns.
入力に、1, 1を与えた時に2回出力が行なわれていますね。これは、片方の端子に1が設定されると、出力は0, 1になり、その後、もう一方の端子に1が設定されると、出力が1, 0となるためです。しかも、どうも順番が変なようです。まず、
out1: 1 at 10ns. out0: 0 at 10ns.
が表示され、次に、
out0: 1 at 10ns. out1: 0 at 10ns.
が表示されていますね。逆ではないのでしょうか? なぜ、こうなっているのか、分かりますか? 考えてみてください。
ちょっと難しかったかもしれません。これはSortedListの挙動が原因です。SortedListに既に同じ値のデータが入っている状態で、データを追加すると、その順番は規定されません。なぜなら二分探索では、中点を調べて、それが探索データと等しければ、そこを発見位置として返してしまうからです。ちょっとテストしてみましょう。
require 'circuit_simulator' class TestData include Comparable def initialize(time, seq) @time = time @seq = seq end def <=>(other) @time <=> other.time end attr_reader :time def to_s "time: #{@time}, seq: #{@seq}" end end list = CircuitSimulator::SortedList.new list.put(TestData.new(0, 0)) list.put(TestData.new(0, 1)) puts("#{list.get}") puts("#{list.get}")
これを実行すると、以下のようになります。
time: 0, seq: 1 time: 0, seq: 0
順番が入れ替わっていますね。2つ目のデータを挿入する際、二分探索で、最初のデータが発見され、その前に挿入するため、このように順番が逆になるわけです。もしも同値のデータがある場合には、その右端に挿入するように、SortedListを変更することにしましょう。
Q: やっと完成かと思っていたら、また問題が見つかってしまいましたね。
A: そうです。プログラミングというのは、最後の最後まで、何が起きるか分かりません。それがプログラミングの難しいところでもあり、楽しいところでもあるのです。
Q: 納期が決まっていたら、楽しんでばかりもいられないです...
A: そうですね。でも、こればっかりは仕方がありません。完璧な設計など不可能なのです。少しでも、こうしたことが起きることを防ぐには、開発の早い段階から、プログラムを徹底的にテストし続けることです。もしも、SortedListを、もっと徹底的にテストしていたら、今回の問題を予見できていたかもしれませんよ。
Q: あと、同じ時刻に入力が行われているのであれば、そもそも2回表示が行われるのは、おかしいのではないですか?
A: 確かにそうです。同一時刻の事象については最終結果のみを返すようにするというのも、1つの考えです。でも、今回の表示は、順番が狂っている点はともかく、2回表示される点は、ある意味正しいのですよ。
Q: というと?
A: 実際の回路では、2つの入力のタイミングを完璧に合わせることは不可能で、必ずズレがあります。なので、実際には、このように出力が、一瞬あばれる状況が起きているのです。これはタイミングチャートで見た時、極く一瞬、値が変化することから縦線のように見えるので「ヒゲ」と呼ばれることがあります。これは、思わぬ回路の誤動作の原因となることもあるので、シミュレータで事前に発見できるのは、ありがたいことでしょう。今回は複数の表示が行われる点については、そのままにすることにします。
83 def put(data) 84 idx = bsearch(data, @table) 85 if idx < 0 86 idx = -idx - 1 # 挿入点 87 else 88 while @table[idx] == data 89 idx = idx + 1 90 break if idx >= @table.size 91 end 92 end 93 94 @table.insert(idx, data) 95 end 96 end
88行目:データが見つかった場合には、データが等しくなくなるか、領域外に出るまで、インデックスを増やすようにしています。
もう一度、SortedListをテストしてみましょう。並べ替えの機能自体が壊れていないかどうかも確認するため、データを増やしています。
... list = CircuitSimulator::SortedList.new list.put(TestData.new(1, 1)) list.put(TestData.new(0, 0)) list.put(TestData.new(1, 0)) list.put(TestData.new(0, 1)) puts("#{list.get}") puts("#{list.get}") puts("#{list.get}") puts("#{list.get}") puts("#{list.get}")
結果は以下のようになりました。
time: 0, seq: 0 time: 0, seq: 1 time: 1, seq: 1 time: 1, seq: 0 ...空行...
ちゃんと順番通りに並び、時刻が同じ場合には、挿入順になっていますね(time = 1の場合は、わざとseqの順序を逆にしてあります)。データが無い時には、nilが返って空行が出力されていることが分かります。これを使って、もう一度半加算器をテストすると以下のようになります。
[0, 0] out1: 0 at 10ns. out0: 0 at 10ns. [0, 1] out1: 0 at 10ns. out0: 0 at 10ns. out0: 1 at 10ns. [1, 0] out1: 0 at 10ns. out0: 1 at 10ns. [1, 1] out1: 0 at 10ns. out0: 1 at 10ns. out1: 1 at 10ns. out0: 0 at 10ns.
今度は、正しい順番で表示されました。
全加算器、4ビット加算器の遅延時間を調べ、データによって遅延時間が異なることを確認し、最悪値を調べてください。
require 'composite_simulator' sim = CircuitSimulator::Simulator.new sim.test_circuit(FullAdder.new(sim)) (sample15/FourBitAdderTest.rb) require 'composite_simulator' sim = CircuitSimulator::Simulator.new sim.test_circuit(FourBitAdder.new(sim))
全加算器の最悪ケースは以下の通り(複数あるうちの1つ):
[0, 1, 1] out0: 1 at 10ns. out1: 0 at 20ns. out0: 0 at 20ns. out1: 1 at 30ns.
4ビット加算器の最悪ケースは以下の通り(複数あるうちの1つ):
[1, 1, 0, 1, 0, 1, 0, 1] out0: 1 at 20ns. out0: 0 at 20ns. out1: 0 at 20ns. out1: 1 at 20ns. out2: 0 at 20ns. out2: 1 at 20ns. out4: 0 at 20ns. out3: 0 at 20ns. out3: 1 at 20ns. out1: 0 at 30ns. out2: 0 at 50ns. out3: 0 at 70ns. out4: 1 at 80ns.
Q: 全加算器の最悪値が30nsなので、それを4つ使った4ビット加算器の最悪値は、30ns x 4 = 120nsかと思っていました。
A: なるほど。そのように単純にいかないので、シミュレータに価値があるわけです。例えば最下位桁の全加算器のキャリー入力は0ですね。全加算器のキャリー入力が0の場合の最悪値を調べてみてください。
Q: あ、キャリー入力が0なら、20nsですね。
A: そうです。各部にテスタを入れて、回路図と見比べてみて、なぜ80nsになるのか調べてみてください。
ご感想をお聞かせください(ruimo@ruimo.com)。なお、誠に勝手ながら、HTMLメールはサーバーで全て削除されますので、テキストメールでお願いいたします。