初心者が学ぶP,NP,NP困難(Hard),NP完全(Complete)とは（わかりやすく解説） - MotoJapan's Tech-Memo
(※訂正のため更新 18/4/23) 論文を読んでいると言葉だけ出会うが、見なかったことにしている言葉なのでちゃんと知りたい。 スタート：全く意味がわかっていないレベル ゴール：論文でその言葉の意味が掴めている状態 言葉の一般的な説明 P NP NP困難 (NP-Hard) NP完全 (NP-Complete) 分かりやすく説明 関係図 問題の難易度 Pの解説 判定問題とは 決定性チューリングマシン（機械）とは 多項式とは 「多項式時間で解ける」とは P読み直し NPの解説 非決定性チューリングマシンとは 「その証拠が本当に正しいかどうかを多項式時間で判定できる」とは NP読み直し NP困難 (NP-Hard)の解説 NP完全 (NP-Complete)の解説 多項式時間還元(polynomial-time reduction)とは 決定性、非決定性チューリングマシンの違い P, NPの違
分岐予測の簡単な歴史 – Part 3 | POSTD
その他 今回、取り上げなかった方法も沢山あります。皆さんの予想どおりかと思いますが、紹介しなかった方法の方が、紹介したものよりずっと多いのです。紹介しなかった方法については、いくつか簡単に説明し、参考サイトを紹介しますので、さらに学びたい場合はそちらを確認してください。 取り上げなかった主要な概念の１つに、 分岐先を予測する方法 が挙げられます。これは、無条件分岐（必ず分岐が成立するため、方向の予測が不要な分岐）にも行う必要がある点に注意してください。なぜなら、 （いくつかの）無条件分岐は分岐先が分からない からです。 分岐先予測はコストが高くなるため、初期のCPU は”常に分岐は不成立だと予測する”という概念を用いていました。なぜなら、分岐が不成立だと予測すれば、分岐先は不要だからです。”分岐は不成立”と常に予測する方式は精度が落ちますが、それでも全く予測しないよりマシです。 干渉低減方
分岐予測の簡単な歴史 – Part 2 | POSTD
2ビット方式 1ビット方式は TTTTTTTT… や NNNNNNN… といったパターンにはうまく働きますが、 ...TTTNTTT... のような「ほとんど成立するが1回だけ不成立」のような分岐の流れでは予測ミスが起きてしまいます。それを改善するために登場したのが、各アドレスに対してもう1ビット追加した飽和カウンタです。では仮に、分岐が不成立だった時はマイナス1、成立した時はプラス1するとしましょう。バイナリ値で見ると以下のようになります。 飽和カウンタの「飽和」とは、 00 にマイナス1した場合はそれ以上値が小さくならずに 00 のまま、 11 にプラス1した場合も 11 のままという動作を取ることを指しています。この方式は1ビット方式とほぼ同一ですが、唯一違うのは予測テーブルの各エントリが1ビットでなく2ビットであるという点です。 1ビット方式に比べると、2ビット方式は同じサイズ/コ
分岐予測の簡単な歴史 - Part 1 | POSTD
※これは、 RC（The Recurse Center：プログラマ教育施設） によって組織された講演シリーズである”localhost”を始動するために、Two Sigma（ツーシグマ）での2017年8月22日の分岐予測に関する講演の原稿を仮に書き起こしたものです。 コードで分岐を使われている方は、どれくらいいらっしゃいますか？ ifステートメントやパターンマッチングを使われているという方、よろしければ手を挙げてください。 ほとんどの聴衆が手を挙げる 次の質問に関しては手を挙げてもらうつもりはありませんが、もしそうお願いした場合、恐らく手を挙げる人の数は少なくなるのではないでしょうか。その質問とは、「分岐を実行する際、CPUが何をして、そのパフォーマンスは何を意味しているのかを十分に理解しているか」、そして「分岐予測に関する最新の論文を理解できるか」というものです。 この講演の目的は、CP
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
