この論文を読む／探す
抄録
並列離散事象シミュレーションに於ける論理プロセス(LP)間の最早時刻印(LTSF)スケジューリング機構として、C_<++>クラスライブラリとしてのヒープを用いたデータ構造を提案する。従来の二進木explicitヒープ構造に基づいているが、dequeue操作を行わずに任意の要素の更新を行うことが出来る。トーナメント形式の木構造で同様な機能を実現するデータ構造が既に提案されているが、LTSFスケジューリングで行われる最高優先度の要素のプライオリティが頻繁に更新される場合に必ずO(logN)のコストがかかるところを、本方式では要素の数が比較的に少ない場合もしくはイベントの大部分が近い将来にスケジュールされる場合においてより小さなコストで実現出来る。また、トーナメント形式に於て必要となる、O(N)の木の再構成のコストが不要である。
A C_<++> class library implementation of priority queue for Least Time Stamp First scheduling of Logical Processes in parallel discrete event simulation is proposed. Although it is based on conventional explicit binary heap, arbitrary element can be updated without dequeue operation. This priority queue performs better than tournament implementation under ordinary event scheduling distribution when the number of items in the queue is relatively small, and when the events are frequently scheduled in the near future. Furthermore, the queue size can always grow and shrink with constant cost as opposed to the tournament implementation where O(N)reorganization cost is needed when the tree have to grow in its depth.
