Search

application/pdf, スレッドライブラリは共有メモリ型マルチプロセサシステムにおいて並行プログラミングを行う標準的な手法の1つである.現在世の中に普及しているスレッドAPIであるPOSIX Thread準拠のものをはじめとする多くのライブラリでは,スレッド間の条件同期の方法として,条件変数(condition variables)を採用している.しかし,条件変数を用いたコード記述は読解しにくく誤りの原因となりやすい.このため,条件変数を1つだけ用意し, すべての条件同期をこの1つの条件変数で待ち合わせる方法が使われることが多い.Java言語における標準の待合せ機構も実質的にはこれに相当する.しかし,この方法ではすべてのスレッドが条件イベントごとに実行を再開し,自分が続行できる条件でない場合は再度待合せに入るため,オーバヘッドが大きい.本論文では,筆者らが考案した抽象状態同期と呼ばれる同期機構をスレッドライブラリAPIに組み込むことを提案する.抽象状態同期では,排他領域により守られているデータ構造の状態を数個の状態に抽象化して考え,そのどれとどれに相当する場合に各操作が領域内に入れるかを指定することで読みやすく効率的なコードを作成できる.本論文では具体的なAPIの提案,その試験実装,性能評価,コードの書きやすさなどについても報告する. Thread libraries are widely used for concurrent programming on shared-memory multiprocessors. On POSIX Thread and other well-known thread libraries, condition variables are used for conditional inter-thread synchronization. However, code with multiple condition variables are difficult to understand and error-prone. Hence, programming style with single condition variable is widely used. Standard synchronization scheme on Java programming languages is effectively designed likewise. However in this scheme, all threads are woken up on each event and have to check for their continuing conditions repeatedly, leading to large overhead. In this paper we propose to incorporate state abstraction-based synchronization into thread libraries. In our scheme, state of the data structure guarded by an mutex is mapped to small number of "abstract states." Every mutex acquisition are guarded by a set of abstract states on which the processing can continue. We also report our API proposal, along with experimental implementation, performance evaluation and some discussion on code readability.

application/pdf, ここ数年WWW上のHTML/XMLデータや、化学物質の構造など、従来の統計・機械学習手法が扱ってきたテーブル形式では表現できないデータを解析したいというニーズが顕在下してきている。GBI(Graph Based Induction)法[1,2]は、そのようなニーズを受け比較的初期から研究が進められてきた色付有向グラフをデータ表現に用いた規則学習手法である。本研究ではGBIのための新しいアルゴリズムとして従来用いられてきたグラフの縮約操作を用いないSEA(Stepwise Entropy Analysis)というアルゴリズムを提案する。 SEAは縮約操作がもたらすGBIのgreedinessを柔らげる事で、学習ルールの精度向上を狙ったアルゴリズムである。さらにSEAのもう1つの特徴である相関ルールと識別ルールの同時学習能力についても報告する。 The importance of analyzing semi-structured data, such as hyper linked WWW text, XML data and chemical formulae, promotes research on a group of data-mining methods which can handle trees, graphs, and other non-table format data. Among these, GBI : Graph Based Induction [1, 2] is one of the incipient methods to extract hidden rules from graph-format data. This paper describes an algorithm, SEA : Stepwise Entropy Analysis, using the GBI method. Though the conventional GBI algorithm contracts with the input graph during the analysis, this new algorithm does not use a contraction operation. Although this new algorithm is still greedy, its greediness is slightly weakened by omitting the contraction operation. Another characteristic of SEA, the simultaneous discovery of the association rule and the classification rule, is also described., 2003-ICS-133-33

application/pdf, 本稿では, 辺彩色グラフ (edge-colored graphs) と呼ぶ, あらかじめ各辺に彩色がなされたグラフの特徴付について議論する. "一般のグラフ"の特徴付けにおいては, ハミルトン閉路といったグラフのもつ構造を鍵として利用している. "辺彩色グラフ"においては, "一般のグラフ"におけるグラフのもつ構造と共に, 交互性 (alternaty) と呼ぶ構造を導入した特徴付けがなされている. 本稿では, 辺彩色グラフにおける交互性を導入したグラフの特徴付けに関する既往の研究を紹介し, さらに, ある特定の点を端点としてもつハミルトン路をもつ辺彩色グラフの特徴付けを示す. An edge-colored graph is a graph, each of whose edge is colored by some color in advance. This paper treats a characterization of edge-colored graphs. To do so, a structure, so-called alternaty, is introduced. This structure is concerning to colors on edges, and plays an important role in characterizations as well as a graphical structure (e.g. Hamiltonian cycle, etc.). We first summarize some previous works concerning to characterizations of edge-colored graphs, and show a characterization of edge-colored graphs based on a new graphical structure.