This document discusses hardware and software requirements for high-performance packet processing. It covers Direct Cache Access (DCA) which allows network cards to directly write received packets to the CPU cache to reduce memory traffic. It also discusses virtualization techniques like Virtual Machine Device Queues (VMDq) and Receive-Side Scaling (RSS) which improve performance by distributing n
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
2. ダブル配列(Double Array)とは • トライ木の実装方法の一つ • トライ木とは？ • 大語彙で前方一致検索を高速に行うことが可能なデータ構造 • 例えば形態素解析、かな漢字変換で利用される • どこが単語の始まりでどこが単語の終わりかわからない時に有用 ハッシュテーブルを使ってルックアップする方法の場合 単語境界がわからないので一文字づつ文字数を増やしてルックアップするしかない 最後までいったら開始点を１文字ずらして再度ルックアップ O(n^2) (入力文字数がn) わ た し の な ま え は な か の で す 。 ・・・ 3. ダブル配列(Double Array)とは • トライ木の実装方法の一つ • トライ木とは？ • 大語彙で前方一致検索を高速に行うことが可能なデータ構造 • 例えば形態素解析、かな漢字変換で利用される • どこが単語の始
「ダブル配列におけるキャッシュの効率化」という論文を見付けた。FIT2006というフォーラムで発表されたものらしい。これはすごい。目から鱗が落ちた。なんかリンク張って良いものか迷うので、とりあえずはリンクしない。 この論文に書いてあることは2つあって、ひとつは配列サイズの削減で、もうひとつはできるだけキャッシュミスを減らすための方法である。配列サイズを削減するための方法がすごい。これまで誰も考え付かなかったのか、それとも考え付いたけどやらなかったのか？ まず、checkの要素サイズは1byteで十分である。なぜなら、遷移元のインデックスがわからなくても、遷移に使ったキーの値がわかれば十分なので。これでDoubleArray全体のサイズを5/8に減らせる。また、普通、1GBのDouble Arrayを作成したりすることは無い（せいぜい100MB程度だろう）ので、Baseにも4byteも割り当
ダブル配列におけるキャッシュの効率化 Cache-Efficienct Double-Array 矢田 晋 森田 和宏 泓田 正雄 平石亘 青江 順一 Susumu Yata Kazuhiro Morita Masao Fuketa Wataru Hiraishi Jun-ichi Aoe 徳島大学工学部 Faculty of Engineering, Tokushima University 1. はじめに 辞書からキーを検索するという処理は，コンパイラ， 索引検索，フィルタリング，形態素解析などの様々な分 野で必要となるため，計算機処理における基礎技術の 一つとされている [1]．特に，文字単位で照合をおこな うトライは，理論的な検索時間がキーの長さで抑えら れる，入力に前方一致するキーを容易に検出できるな どの理由から，自然言語辞書を中心として幅広く利用 されている．このトライを実現す
ところがこのリスト、RIR statistics exchange format にも書いてあるように、「開始 IP アドレスから何個」という表現になっているので、そのままではサブネット マスクや CIDR の表現としては使えないレコードがあります。例えば、 192.168.0.0 から 768 個 768 個を表すサブネット マスクはない。 したがって、192.168.0.0/255.255.254.0 と 192.168.2.0/255.255.255.0 の二つに分けなければならない。 192.168.3.0 から 512 個 512 個なのでサブネット マスクは 255.255.254.0 だが、ホスト アドレス部が 0 になっていないため、単純に 192.168.3.0/255.255.254.0 とすることができない。 したがって、192.168.3.0/255.255.255
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
