- 【FPGA/CPLD】 XILINX/ALTERA/Lattice/Actel #24 [無断転載禁止]©2ch.net
927 ：774ワット発電中さん[]：2017/11/25(土) 13:37:20.37 ID:Z+1XQz7p - 概要：添付の図(https://imgur.com/a/tiPiJ)のような樹形図回路を用意、
分岐をある地点からの選択肢とする。
また、地点と地点の間は距離に見合った（比例した値の）抵抗を置く。
そして中心から電気を流し、末端に流れる電流量の最大を測定するなり、
アナログ的に比較するなりして最大値を求める。
これを地点数の分だけ繰り返し、それぞれの最大値を取った経路のみをパソコンで演算すれば
格段に演算量が少なくなる。
原理：アナログ回路を上記のように組めば、電気が伝わる速さで結果が出せる。
（抵抗値の合計が最も少ない経路に、最も多くの電流が流れるため、演算の必要なし。）
ただし、とても多くの可変抵抗を組み込んだ専用回路を必要とする。
可変抵抗数は簡単な計算の結果、総当たりに必要なパターン数の約三倍くらい必要な模様。
|
- 【FPGA/CPLD】 XILINX/ALTERA/Lattice/Actel #24 [無断転載禁止]©2ch.net
928 ：774ワット発電中さん[]：2017/11/25(土) 13:37:46.92 ID:Z+1XQz7p - 利点と問題点：
概要に記載したようにすると、パソコンによる地点数ぶんの演算は必要だが、
初めから全パターンを探索も可能。
（ただし、完全なる逆走パターンも同じ値をとるため、その検出が面倒かと思った。
また、可変抵抗数はさらに「×地点数」という量が必要になる。）
メモリ領域へのアクセス数が明らかに減る。
現在のパソコンだと、
1.メモリからの読み込み
2.cpuの演算
3.メモリへ演算結果の書き込み
という工程が必要だが、
このfpga的なものだと
1.メモリへのアクセス
だけで終わる。
また抵抗値の値のパターンは「地点数C2(2は小文字)=地点数×(地点数-1)/2」パターンしかないので、
かなり前の世代のcpuのキャッシュ領域ですら保存できる可能性が高い。
(もちろん地点数をあほみたいに増やせばあふれるけど)
つまり高速アクセスが可能。
ここから先はキャッシュ領域やバス幅を増やせば加速度的に早くなるけど、割愛。
|
- 【FPGA/CPLD】 XILINX/ALTERA/Lattice/Actel #24 [無断転載禁止]©2ch.net
929 ：774ワット発電中さん[]：2017/11/25(土) 13:38:11.85 ID:Z+1XQz7p - 要約：
総当たり演算の代わりに多数の可変抵抗を準備というトレードオフによって結果を求める。
しかし、可変抵抗の準備にかかる時間は現行技術で十分高速化が可能ある。
演算時間において、デメリットよりメリットのほうが大きいため、
かなりな高速化（地点数が十分多いときにおいて）が見込まれる。
問題点として、汎用性が低いこと、製造コストが少し高めになってしまうこと、
などが考えられる。
補足：
図の場合だと、5点を巡回するので、
初めにある点をスタートと決め、
次の選択肢は四つあることになる。
|
- 【FPGA/CPLD】 XILINX/ALTERA/Lattice/Actel #24 [無断転載禁止]©2ch.net
930 ：774ワット発電中さん[]：2017/11/25(土) 13:41:46.40 ID:Z+1XQz7p - と、考えてみたのだが、どうだろうか？
|
- 【FPGA/CPLD】 XILINX/ALTERA/Lattice/Actel #24 [無断転載禁止]©2ch.net
932 ：774ワット発電中さん[]：2017/11/25(土) 15:00:24.75 ID:Z+1XQz7p - 総パターン数のおよそ三倍ということに間違いがない場合、
10地点で1000万個ぐらい。
20だと7500000000000000000個ぐらいかな。
ちなみにCPUのトランジスタ数が
5500万個という記述があったので、
（https://oshiete.goo.ne.jp/qa/7602697.html）
11地点までくらいなら作れなくはないかも程度。
ちなみに、http://www.geocities.jp/m_hiroi/light/pyalgo62.html
に記載されている感じだと11地点で6分ぐらいかかりそうなので、
技術的な落としどころ(製造可能な範囲)と、社会的なニーズ（6分判断待ちはできない）
が合いそう。
また、明らかにあり得ない組み合わせを排除するアルゴリズムが
何個か開発されていたはずなので、
それを用いると抵抗の数を減らせるはず。
あるいはパターン分けを行うという手もある。
例えば明らかに離れた二つの集団(10+10)がある場合、
初めに片方の集団だけを検討し、次にもう一方の集団だけを検討、
最後に総合評価で出せば、20地点でも対応できる。
（さすがにこれは都合がよすぎる場合だけど）
|
- 【FPGA/CPLD】 XILINX/ALTERA/Lattice/Actel #24 [無断転載禁止]©2ch.net
934 ：774ワット発電中さん[]：2017/11/25(土) 15:44:25.14 ID:Z+1XQz7p - ＞分枝限定法は探索木を深さ優先で直列に調べていって
＞調べる必要がないと確定した枝は破棄する方法なので、
＞完全並列を目指すこの方法にはほとんど適用できないよ。
そうなんですか・・・
不勉強でした。申し訳ないです。
例えば、11地点用の回路が製造できたとして、13地点で検証したい場合、
13×12回この回路を回せば、そのあとに13×12通りの演算をパソコンですればいいだけになる
と思うのですが、その場合の計算数を減らせるかな、とも考えていました。
ただ、この場合演算数が少ないので、わざわざ別プログラムでやる必要がないですね。
＞あと、最後の比較もちゃんと考えないと死ぬよ。
そうなんですよね・・・
24bitで計測可能、18bitまでは確実に正確！
みたいな計測IC的なものを用いたほうが楽ですかね？
上位ビットから確認していって、一番「1」が続くものをピックアップみたいな感じで。
|