Ruby 3 動的回路シミュレータの解答例

この内容は「Ruby 3 オブジェクト指向とはじめての設計」で取り上げた、動的回路シミュレータの最終形の1解答例です。ページの関係で、あふれてしまったので、ここに公開します。

ここにある文書が正しかったこと、正しくなかったことによって生じたあらゆる結果に対して、当方は一切の保証を行いません。

最終更新日 2009/8/23

動的回路シミュレータを完成させる。

入力の全パターンを与えて、素子の遅延時間を測定することが目的でしたが、本書の中で解説したプログラムでは、オブザーバパターンを用いているため、出力が変化しないとテスタが呼び出されず、遅延時間の測定ができない問題がありました。

これを解決するには2つの方法が考えられます。1つ目は、入力パターンが変わるごとに全てのデバイスを作り直すという方法、もう1つは、状態をリセットする手段を用意して、全端子の状態をnilに戻せるようにする方法です。

全てのデバイスを作り直すという方法は、若干オーバーヘッドがありますが、悪い方法ではありません。毎回オブジェクトが新規に生成されるので、確実に状態を初期状態に戻すことができます。今回はデバイスを引数に渡してやれば、そのデバイスに全ての入力パターンを与えるメソッドを、Simulatorに作成することを予定しています。全てのデバイスを作り直すのだとすると、回路の組み立て処理を何らかの形で、このメソッドに渡さなければなりません(おそらくはブロックで渡すことになるでしょう)。これは呼び出す側にとっては、面倒です。そこで今回は後者の方法をとることにします。

全Terminalの状態をnilにリセットする機能を作成することにします。まずSimulatorで、生成した全てのデバイスを管理できるようにします。そのために、

  1. SimulatorにLogicDeviceを保存するための配列を用意します。
  2. registerDeviceメソッドを用意し、引数で渡されたLogicDeviceを、1.で作成した配列に追加します。
  3. resetメソッドを用意します。これは、@current_timeを0とし、配列に保持している全LogicDeviceのインスタンスのresetを呼び出して、全デバイスのリセットを行います。
  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になるのか調べてみてください。


Valid XHTML 1.0 Strict

 ご感想をお聞かせください(ruimo@ruimo.com)。なお、誠に勝手ながら、HTMLメールはサーバーで全て削除されますので、テキストメールでお願いいたします。

 書きもののページへ

 トップページへ