跳到主要内容

東京大学 情報理工学系研究科 創造情報学専攻 2018年8月実施 筆記試験 第2問

Author​

tomfluff

Description​

太陽光発電システムについて考えよう。ソーラーパネルの維持管理のため、以下のような運用規則が定められているとする。

  • (i) 枚のパネルが一つのグループとして維持管理される。
  • (ii) パネルはグループごとに定期的に点検される。
  • (iii) パネルの状態は各グループごとに ビットデータとして報告される。

ここで各ビットは対応するパネルに不具合があれば 、不具合がなければ とする。 不具合のあるパネルの数、すなわちビットデータの の個数 を数える “population count” 問題を考えよう。以下の設問に答えよ。

まず、ソフトウェアによる解法を考えよ。ここでは、、 とする。
四則演算、論理演算、シフト演算、および表引きには 単位時間かかるとする。単純化のため、インデックスの足し算やループで用いる比較演算の演算時間はゼロとする。

(1) 単純な方式として各ビットの値をチェックし、 の個数の総和を求める方式が考えられる。この方式の疑似コードを書き、その計算時間を答えよ。

(2) 実際、表引き操作を行うことで上述の方式 (1) を高速化できる。その計算時間を答えよ。

(3) 方式 (1) より高速かつ方式 (2) よりストレージを必要としない方式の擬似コードを示せ。その計算時間を答えよ。

ハードウェアによる解決を考えよう。ここでは、入力はビット列、出力は 進数とする。

(4) 入力 ビットの population count 論理回路 の真理値表を書け。AND、OR、NOT ゲートを用いて を設計せよ。

(5) 入力 ビットの population count 論理回路 を論理回路 を利用して作成せよ。必要に応じて、追加で AND、OR、NOT ゲートを使っても良い。*

(6) 入力 ビットの population count 論理回路 を考える時、 が増えると遅延が問題となる。この問題を解決する方法を述べよ。

Kai​

(1)​

k = 0
i = 0
while i < 32:
    k = k + (1 & n) // (2 time units)
    n = n >> 1 // shift to the right (1 time unit)
    i = i + 1
return k

Time complexity would be in the general case since we go over every indicator once. In this case since then it will be . Exact computation time would be units of time.

(2)​

In the case where we use lookup tables we can save the shift operation. This means that the computation time would be: units of time.

(3)​

k = 0
i = 1
while i < 2**32:
    k = k + (i & n) // (2 time units)
    i = i << 1
return k

In this method we take only units of time as (2) but we use less space than with a lookup table. We took advantage of the loop indicator as the mask for the logical and operation.

(4)​

Let us use AND, OR and NOT to define a new gate called XOR.

Using XOR, AND, OR and NOT we will creatre P3 as follows:

The truth table for it would be:

In0In1In2Out0Out1
00000
00110
01010
01101
10010
10101
11001
11111

(5)​

For P6 the logic will be as follows:

(6)​

Note: I am not sure about my answer, I think propogation delay is correct but not sure. The question itself isn't clear as well. Should I solve the latency problem or give a reason. Not clear.

Since any of the elements could contribute to the actual sum, there would be a large number of gates which need the data from the last gates available. That is, there would be many in-line gates which would need to wait for the correct value to propogate forward.

目录