図面 (/)

技術 命令トレース生成プログラム、命令トレース生成装置および命令トレース生成方法

出願人 富士通株式会社
発明者 成瀬彰
出願日 2008年6月26日 (11年2ヶ月経過) 出願番号 2008-167284
公開日 2010年1月14日 (9年8ヶ月経過) 公開番号 2010-009282
状態 特許登録済
技術分野 デバッグ/監視
主要キーワード 時間重み 尤度算出処理 性能最適化 度得点 ベーシックブロック ネットワークインターフェース装置 組合せパターン 生成用データ
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2010年1月14日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

オーバヘッドを軽減するために命令採取する頻度下げた場合でも正確な命令トレースを生成すること。

解決手段

分割部112は、プロセッサが実行する命令を所定間隔サンプリングして得られたサンプリングデータ121を、命令トレースの取得対象命令列が1回実行される間に取得された単位の部分命令列122へ分割する。そして、部分命令列122は、合成制御部113の制御によって、類似度尤度に基づいて1つに合成され、命令トレース出力部114によって出力される。

概要

背景

従来より、動作するプログラム性能最適化デバッグ等を目的として、命令トレースを取得する技術が知られている。命令トレースとは、プロセッサによって実行された個々の命令を時系列に記録したデータである。命令トレースを参照することにより、プロセッサが、プログラムを動作させるために、どの命令をどの順序で実行しているかを詳細に把握することができ、性能最適化等のための適切な対策を講じることが可能になる。

このように命令トレースを取得することは、プログラムの性能最適化等において非常に有効な手法であるが、命令トレースを取得するためにオーバヘッドが生じてしまうという弊害がある。例えば、1命令毎に割込みをかけて命令トレースを取得することとした場合、このオーバヘッドのためにプログラムの実行時間が数百〜数千倍になることがある。命令トレースの取得時のプログラムの実行時間が通常時とこれだけ異なってしまうと、取得された命令トレースは、プログラムの通常時の挙動を正しく反映しているとは言えず、プログラムの挙動を把握する情報として不適切なものとなる。

命令トレースの取得時のプログラムのオーバヘッドを軽減するための技術として、全ての命令のトレースを取得するのではなく、分岐命令のみのトレースを取得する技術が知られている。プログラムの命令列における分岐命令の出現頻度が10命令に1つ程度であるとすると、分岐命令のみのトレースを取得することにより、オーバヘッドを1/10程度に減らすことができる。また、分岐命令のトレースを取得しておけば、分岐命令が実行される間にどの命令がどの順序で実行されたかについては、分岐命令のトレースとプログラム中の命令列を比較することによりある程度推定することができる。

特開2002−342114号公報

概要

オーバヘッドを軽減するために命令を採取する頻度下げた場合でも正確な命令トレースを生成すること。分割部112は、プロセッサが実行する命令を所定間隔サンプリングして得られたサンプリングデータ121を、命令トレースの取得対象の命令列が1回実行される間に取得された単位の部分命令列122へ分割する。そして、部分命令列122は、合成制御部113の制御によって、類似度尤度に基づいて1つに合成され、命令トレース出力部114によって出力される。

目的

開示の技術は、上述した従来技術による問題点を解消するためになされたものであり、オーバヘッドを軽減するために命令を採取する頻度を下げた場合でも正確な命令トレースを生成することができる命令トレース生成プログラム命令トレース生成装置および命令トレース生成方法を提供することを目的とする。

効果

実績

技術文献被引用数
1件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

複数回実行される第1の命令列所定間隔サンプリングして得られた第2の命令列から、該第1の命令列の命令トレースを生成する命令トレース生成プログラムであって、前記第2の命令列を、部分命令列に分割し、分割された各部分命令列を記憶手段に記憶させる分割手順と、前記記憶手段に記憶された全ての部分命令列の組合せ毎類似度を算出する類似度算出手順と、前記類似度算出手順によって算出された類似度に基づいて部分命令列の組合せを選択する選択手順と、前記選択手順によって選択された部分命令列に含まれる命令を組み合わせて複数の組合せパターンを生成する組合せパターン生成手順と、前記組合せパターン生成手順によって生成された組合せパターン毎に尤度を算出する尤度算出手順と、前記尤度算出手順によって算出された尤度に基づいて組合せパターンを前記記憶手段に記憶させる部分命令列置換手順とをコンピュータに実行させることを特徴とする命令トレース生成プログラム。

請求項2

合成制御手順をコンピュータにさらに実行させ、前記選択手順は、前記類似度算出手順によって算出された類似度が最も高い部分命令列の組合せを選択し、前記部分命令列置換手順は、前記尤度算出手順によって算出された尤度が最も高い組合せパターンを、前記選択手順によって選択された部分文字列に代えて、部分文字列として前記記憶手段に記憶させ、前記合成制御手順は、前記記憶手段に記憶される部分命令列が1つになるまで、前記類似度算出手順と、前記選択手順と、前記組合せパターン生成手順と、前記部分命令列置換手順とを制御することを特徴とする請求項1に記載の命令トレース生成プログラム。

請求項3

前記類似度算出手順は、部分命令列に含まれる命令が属する関数の関数名と、該関数の先頭からの該命令のオフセットとに基づいて類似度を算出することを特徴とする請求項1または2に記載の命令トレース生成プログラム。

請求項4

前記尤度算出手順は、部分命令列に含まれる命令が属する関数の関数名と、該関数の先頭からの該命令のオフセットとに基づいて尤度を算出することを特徴とする請求項1から3のいずれか1つに記載の命令トレース生成プログラム。

請求項5

複数回実行される第1の命令列を所定間隔でサンプリングして得られた第2の命令列から、該第1の命令列の命令トレースを生成する命令トレース生成装置であって、前記第2の命令列を、部分命令列に分割し、分割された各部分命令列を記憶手段に記憶させる分割手段と、前記記憶手段に記憶された全ての部分命令列の組合せ毎に類似度を算出する類似度算出手段と、前記類似度算出手段によって算出された類似度に基づいて部分命令列の組合せを選択する選択手段と、前記選択手段によって選択された部分命令列に含まれる命令を組み合わせて複数の組合せパターンを生成する組合せパターン生成手段と、前記組合せパターン生成手段によって生成された組合せパターン毎に尤度を算出する尤度算出手段と、前記尤度算出手段によって算出された尤度に基づいて組合せパターンを前記記憶手段に記憶させる部分命令列置換手段とを備えることを特徴とする命令トレース生成装置。

請求項6

複数回実行される第1の命令列を所定間隔でサンプリングして得られた第2の命令列から、該第1の命令列の命令トレースを生成する命令トレース生成方法であって、前記第2の命令列を、部分命令列に分割し、分割された各部分命令列を記憶手段に記憶させる分割工程と、前記記憶手段に記憶された全ての部分命令列の組合せ毎に類似度を算出する類似度算出工程と、前記類似度算出工程によって算出された類似度に基づいて部分命令列の組合せを選択する選択工程と、前記選択工程によって選択された部分命令列に含まれる命令を組み合わせて複数の組合せパターンを生成する組合せパターン生成工程と、前記組合せパターン生成工程によって生成された組合せパターン毎に尤度を算出する尤度算出工程と、前記尤度算出工程によって算出された尤度に基づいて組合せパターンを前記記憶手段に記憶させる部分命令列置換工程とを含むことを特徴とする命令トレース生成方法。

技術分野

0001

この発明は、命令トレースを生成する命令トレース生成プログラム命令トレース生成装置および命令トレース生成方法に関する。

背景技術

0002

従来より、動作するプログラム性能最適化デバッグ等を目的として、命令トレースを取得する技術が知られている。命令トレースとは、プロセッサによって実行された個々の命令を時系列に記録したデータである。命令トレースを参照することにより、プロセッサが、プログラムを動作させるために、どの命令をどの順序で実行しているかを詳細に把握することができ、性能最適化等のための適切な対策を講じることが可能になる。

0003

このように命令トレースを取得することは、プログラムの性能最適化等において非常に有効な手法であるが、命令トレースを取得するためにオーバヘッドが生じてしまうという弊害がある。例えば、1命令毎に割込みをかけて命令トレースを取得することとした場合、このオーバヘッドのためにプログラムの実行時間が数百〜数千倍になることがある。命令トレースの取得時のプログラムの実行時間が通常時とこれだけ異なってしまうと、取得された命令トレースは、プログラムの通常時の挙動を正しく反映しているとは言えず、プログラムの挙動を把握する情報として不適切なものとなる。

0004

命令トレースの取得時のプログラムのオーバヘッドを軽減するための技術として、全ての命令のトレースを取得するのではなく、分岐命令のみのトレースを取得する技術が知られている。プログラムの命令列における分岐命令の出現頻度が10命令に1つ程度であるとすると、分岐命令のみのトレースを取得することにより、オーバヘッドを1/10程度に減らすことができる。また、分岐命令のトレースを取得しておけば、分岐命令が実行される間にどの命令がどの順序で実行されたかについては、分岐命令のトレースとプログラム中の命令列を比較することによりある程度推定することができる。

0005

特開2002−342114号公報

発明が解決しようとする課題

0006

しかしながら、分岐命令のみのトレースを取得することによって、オーバヘッドを1/10程度に減らすことができたとしても、プログラムによっては、トレース取得時の挙動が通常時と異なってしまうことがあった。そこで、トレースを取得する頻度をさらに下げてオーバヘッドを軽減することが考えられるが、その場合、採取された命令間でどのような命令がどの順序で実行されたかを推定することが困難になるという問題があった。

0007

開示の技術は、上述した従来技術による問題点を解消するためになされたものであり、オーバヘッドを軽減するために命令を採取する頻度を下げた場合でも正確な命令トレースを生成することができる命令トレース生成プログラム、命令トレース生成装置および命令トレース生成方法を提供することを目的とする。

課題を解決するための手段

0008

上述した課題を解決し、目的を達成するため、本願の開示する命令トレース生成装置は、一つの態様において、複数回実行される第1の命令列を所定間隔サンプリングして得られた第2の命令列から、該第1の命令列の命令トレースを生成する命令トレース生成装置であって、前記第2の命令列を、部分命令列に分割し、分割された各部分命令列を記憶手段に記憶させる分割手段と、前記記憶手段に記憶された全ての部分命令列の組合せ毎類似度を算出する類似度算出手段と、前記類似度算出手段によって算出された類似度に基づいて部分命令列の組合せを選択する選択手段と、前記選択手段によって選択された部分命令列に含まれる命令を組み合わせて複数の組合せパターンを生成する組合せパターン生成手段と、前記組合せパターン生成手段によって生成された組合せパターン毎に尤度を算出する尤度算出手段と、前記尤度算出手段によって算出された尤度に基づいて組合せパターンを前記記憶手段に記憶させる部分命令列置換手段とを備える。

0009

この命令トレース生成装置の態様によれば、プロセッサによって実行された命令を、所定の間隔でサンプリングして得られたサンプリングデータを部分命令列に分割し、類似度と尤度に基づいて合成して命令トレースを生成することとしたので、実行中のプログラムの挙動に影響がない程度に情報を取得する頻度を下げつつ、所望する命令トレースを正確に取得することができる。

発明の効果

0010

本願の開示する命令トレース生成プログラム、命令トレース生成装置および命令トレース生成方法の一つの態様によれば、オーバヘッドを軽減するために命令を採取する頻度を下げた場合でも正確な命令トレースを生成することができるという効果を奏する。

発明を実施するための最良の形態

0011

以下に添付図面を参照して、本願の開示する命令トレース生成プログラム、命令トレース生成装置および命令トレース生成方法の好適な実施の形態を詳細に説明する。

0012

まず、本実施例に係る命令トレース生成方法の概要について説明する。本実施例に係る命令トレース生成方法は、オーバヘッドを軽減するためにトレース頻度を下げた場合であっても、どの命令がどの順序で実行されたかを高い精度で再現した命令トレースを取得することを実現する。

0013

具体的には、本実施例に係る命令トレース生成方法は、プロセッサによって実行される命令を所定の間隔で取得して得られたサンプリングデータに基づいて、命令トレースを生成する。プロセッサによって実行される命令を取得する間隔を十分に大きくすることにより、オーバヘッドを軽減し、実行時間の変化によるプログラムの挙動の変化を抑制することができる。

0014

上記のようにサンプリングデータに基づいて命令トレースを生成するため、本実施例に係る命令トレース生成方法は、命令トレースの取得対象の命令列が再現性を有することを前提とする。ここでいう再現性とは、トレースの取得対象の命令列を複数回実行した場合に、それぞれの回において、命令列中の命令が同じ順序で実行されることを意味する。

0015

なお、トレースの取得対象のプログラムは、再現性を有するように予めプログラミングされている必要は必ずしもない。すなわち、再現性は、例えば、プログラムに入力するデータを毎回同じものにするというように、プログラムの動作条件を毎回同じにすることによって実現されてもよい。また、命令トレースの取得対象の命令列は、プログラムに含まれる命令列全体でもよいし、その一部であってもよい。

0016

以下に、具体例を示しながら、本実施例に係る命令トレース生成方法について説明する。図1は、プログラムの一例を示す図である。図1に示したプログラムは、main()という関数と、func_M()という関数を含んでいる。main()は、プログラムが起動されると最初に実行される関数であり、func_M()を無限回数呼び出す。func_M()は、func_A()を1回呼び出した後、func_B()を3回呼び出し、その後、func_C()を1回呼び出す。

0017

ここでは、図1に示したプログラムにおけるfunc_M()の部分をトレースの取得対象とし、この部分が再現性を有しているものとする。また、func_M()において実行されるfunc_A()、func_B()およびfunc_C()は、それぞれ10個の命令を有するものとする。また、これらの関数には分岐命令が存在しないものとする。

0018

図2は、命令のサンプリングの一例を示す図である。本実施例において各命令に付与されている文字列の「:」よりも前の部分は、その命令が属している関数の名称を表し、「:」よりも後ろの部分は、関数の先頭を基準とした場合のその命令のオフセット(以下「関数内オフセット」という)を表す。例えば、「func_A:0」は、func_A()という名前の関数における先頭の命令であることを示す。

0019

図1に示したプログラムを動作させると、func_M()が複数回呼び出され、図2に示した命令列11がプロセッサによって実行される。すなわち、func_M()が1回目に呼び出されたときに、func_A()に相当する10個の命令が1回実行され、func_B()に相当する10個の命令が3回実行され、func_C()に相当する10個の命令が1回実行される。そして、func_M()が2回目の以降に呼び出された場合も、1回目と同じ命令が同じ順序でプロセッサによって実行される。なお、説明を簡単にするため、func_B()を3回実行するためのループ処理や、関数の呼び出しや復帰のための命令は無視することとする。

0020

命令列11は、命令トレースに相当する命令列であるが、プロセッサが命令を1つ実行する毎に情報を取得したのではオーバヘッドが大きくなり、プログラムの挙動に影響を与える。そこで、ここでは、プロセッサによって実行される命令を7個毎にサンプリングすることとする。なお、サンプリング間隔を7とするのは一例であり、サンプリング間隔は、オーバヘッドが十分に小さくなる任意の値とすることができる。

0021

func_M()を何度も呼び出しながら、命令を7個毎にサンプリングすることにより、図2および図3に示すようなサンプリングデータ21が得られる。サンプリングデータ21は、命令トレースの取得対象であるfunc_M()が1回呼び出された場合にプロセッサによって実行される命令数分の命令を含んでいる。具体的には、func_M()が1回呼び出された場合、上記の通り50個の命令がプロセッサによって実行されるが、サンプリングデータ21は、50個の命令を含んでいる。こうしてサンプリングデータ21が取得された時点で、図1に示したプログラムの実行を停止して構わない。

0022

こうしてサンプリングデータ21が得られた後、サンプリングデータ21が部分命令列に分割される。具体的には、本実施例に係る命令トレース生成方法では、サンプリングデータ21が、命令トレースの取得対象であるfunc_M()が1回呼び出された間に取得された単位でサンプリングデータ21が部分命令列に分割される。

0023

図4は、分割命令列の一例を示す図である。図4に示すように、サンプリングデータ21は、P−1〜P−7という7つの部分命令列に分割される。P−1は、func_M()が1回目に呼び出されたときにサンプリングによって得られた命令列であり、P−2は、func_M()が2回目に呼び出されたときにサンプリングによって得られた命令列である。

0024

続いて、部分命令列の組合せ毎に類似度が算出される。なお、ここでいう類似度は、最終的に得られる命令トレースにおいて隣り合う関係にある可能性が高い部分命令列の組合せほど高く評価され、完全一致の場合に最も高くなるわけではない。

0025

例えば、
「func_A:0」と「func_A:7」
という2つの命令を含む部分命令列Aと、
「func_A:0」と「func_A:7」
という2つの命令を含む部分命令列Bと、
「func_A:1」と「func_A:8」
という2つの命令を含む部分命令列Cとがあったものとする。

0026

この場合、最終的に得られる命令トレースにおいて、命令が、
「func_A:0」、「func_A:0」
という順序で隣り合って並び、その後方で、
「func_A:7」、「func_A:7」
という順序で隣り合って並ぶ可能性よりも、命令が、
「func_A:0」、「func_A:1」
という順序で隣り合って並び、その後方で、
「func_A:7」、「func_A:8」
という順序で隣り合って並ぶ可能性が高い。このため、上記の例の場合、部分命令列Aと部分命令列Bの組合せよりも、部分命令列Aと部分命令列Cの組合せの方が類似度が高いと評価される。

0027

部分命令列の組合せの類似度は、各部分命令列に含まれる命令を先頭から順に比較して得られた命令単位の類似度を合計することにより算出される。そして、命令単位の類似度は、命令の関数名が一致し、関数内オフセットの差分の絶対値が1に近いほど高く評価される。一方、命令の関数名が一致しない場合や、命令の関数名が一致しても関数内オフセットの差分が大きい場合には、命令単位の類似度は、低く評価される。図5は、類似度の算出結果の一例を示す図である。図5に示すように、類似度は、全ての部分命令列の組合せについて算出される。

0028

続いて、算出された類似度が最も高い部分命令列の組合せが選択される。例えば、類似度の算出結果が図5に示した通りであるとすると、P−4とP−5の組合せが、類似度が最も高い部分命令列の組合せとして選択される。

0029

そして、選択された組合せに含まれる2つの部分命令列が1つに合成される。部分命令列の合成は、それぞれの部分命令列に含まれる命令を交互に組み合わせた複数の組合せパターンを生成し、その中から最も尤度が高いものを選択することにより行われる。そして、合成前の2つの部分命令列は、合成後の部分命令列に置き換えられる。なお、ここでいう尤度は、命令の並びの尤もらしさを意味する。

0030

なお、類似度が最も高い部分命令列の組合せのみを合成して尤度を算出するのではなく、類似度が高い順に部分命令列の組合せを所定の個数だけ選択し、組合せ毎に組合せパターンを生成し、最も高い尤度が得られた組合せを置き換えることとしてもよい。例えば、複数の組合せのうち、部分文字列AとBの組合せを合成した組合せパターンCが最も尤度が高ければ、部分文字列AとBを組合せパターンCに置き換えることとしてもよい。

0031

図6は、部分命令列の合成の一例を示す図である。図6に示すように、まず、選択されたP−4とP−5という2つの部分命令列に基づいて、P−4に含まれる命令が先になるように命令を交互に組み合わせたP−4−5と、P−5に含まれる命令が先になるように命令を交互に組み合わせたP−5−4とが生成される。そして、生成されたP−4−5とP−5−4の尤度がそれぞれ算出される。

0032

尤度は、部分命令列の先頭から前後する命令を比較して命令単位の尤度を算出していき、命令単位の尤度を合計することにより算出される。そして、命令単位の尤度は、命令の関数名が一致し、関数内オフセットの値が昇順に並んでいてその差分が1に近いほど高く評価される。一方、命令の関数名が一致しない場合、命令の関数名が一致しても関数内オフセットの値が降順の場合、命令の関数名が一致して関数内オフセットの値が昇順であってもその差分が大きい場合には、命令単位の尤度は、低く評価される。命令列の順序が実行順序の通りであれば、前後の命令の関数名が一致し、オフセットの値が昇順になることが多いはずだからである。

0033

図6に示した例では、関数内オフセットの値が昇順に並んでいるものが多いP−5−4が選択され、P−4およびP−5と置き換えられる。その後、再び、部分命令列の組合せの類似度が算出され、最も類似度の高い組合せが合成され、合成前の2つの部分命令列が、合成後の部分命令列に置き換えられる。この処理を繰り返し実行することにより、最終的に部分命令列は1つに合成されることになる。このようにして合成された命令列は、図2に示した命令列11の1回目の部分、すなわち、取得すべき命令トレースと同じものとなることが期待できる。

0034

ここで、部分命令列の合成についてさらに詳しく説明しておく。合成対象の部分命令列の一方、もしくは、双方が部分命令列を合成して得られたものである場合、合成して得られた部分命令列は、いったん分割当初の部分命令列に分割され、その後、組合せパターンが生成される。このとき、組合せパターンは、既に合成された部分命令列の順序が変化しないように生成される。例えば、図7に示すように、まだ合成されていないP−7と、P−5が先頭になるようにP−4とP−5を合成して得られたP−5−4とを合成する場合、P−4がP−5よりも前にならないように組合せパターンが生成される。

0035

すなわち、図7の例の場合、P−7、P−5、P−4の順に命令を交互に組み合わせたP−7−5−4や、P−5、P−7、P−4の順に命令を交互に組み合わせたP−5−7−4や、P−5、P−4、P−7の順に命令を交互に組み合わせたP−5−4−7が組合せパターンとして生成される。一方、P−4、P−5、P−7の順に命令を交互に組み合わせるといったように、P−4がP−5よりも前に位置する組合せパターンは生成されない。

0036

次に、本実施例に係る命令トレース生成方法を実行する命令トレース生成装置の構成について説明する。図8は、本実施例に係る命令トレース生成装置100の構成を示す機能ブロック図である。図8に示すように、命令トレース生成装置100は、制御部110と、記憶部120とを有する。

0037

制御部110は、命令トレース生成装置100を全体制御する制御部であり、命令情報設定部111と、分割部112と、合成制御部113と、類似度算出部113aと、選択部113bと、組合せパターン生成部113cと、尤度算出部113dと、部分命令列置換部113eと、命令トレース出力部114とを有する。

0038

命令情報設定部111は、記憶部120に記憶されているサンプリングデータ121に対して命令情報を設定する。サンプリングデータ121は、命令トレースの取得対象の命令列を複数回実行している間にプロセッサによって実行された命令を所定間隔でサンプリングして得られたデータであり、命令トレースを生成するために十分な数の命令を含んでいる。

0039

具体的には、命令情報設定部111は、サンプリングデータ121に含まれる命令毎にその命令が属する関数の関数名とその命令の関数内オフセットを取得し、取得された関数名と関数内オフセットをその命令に対応付けて命令情報として設定する。なお、関数名と関数内オフセットは、例えば、命令のアドレスをプログラム中のシンボルテーブルと照合することによって取得することができる。

0040

分割部112は、命令トレースの取得対象の命令列が1回実行される間にサンプリングされた単位で、サンプリングデータ121を複数の部分命令列122に分割して記憶部120に格納する。例えば、命令トレースの取得対象の命令列の命令数をTとし、サンプリング間隔をPとした場合、T/P個毎にサンプリングデータ121を分割していくことにより、上記の単位での分割を容易に行うことができる。なお、命令トレースの取得対象の命令列における先頭付近の関数がわかっていれば、その関数を基準として、サンプリングデータ121を上記の単位で分割することもできる。また、分割の基準とするための関数もしくは命令列をプログラムに含めておき、それらを基準としてサンプリングデータ121を分割することもできる。また、これらの方式を任意に組み合わせることもできる。

0041

合成制御部113は、分割部112によって分割された部分命令列122が適切な順序で1つに合成されるまで、類似度算出部113a、選択部113b、組合せパターン生成部113c、尤度算出部113dおよび部分命令列置換部113eを制御する。

0042

類似度算出部113aは、部分命令列122の組合せの全てについて類似度を算出する。類似度は、各部分命令列122に含まれる命令を先頭から順に比較し、比較結果を類似度得点データ124と照合して得られた得点(命令単位の類似度)を合計することにより算出される。

0043

類似度得点データ124の一例を図9に示す。図9に示すように、類似度得点データ124には、関数名が一致した場合の得点として「10」が設定され、関数名が不一致であった場合の得点として、それよりも低い「0」が設定されている。また、関数名が一致した場合に関数内オフセットの差分に基づいて与えられる得点として、差分の絶対値が「1」に近いほど高い値が設定されている。差分の絶対値が「1」に近いほど、前後して実行された命令である可能性が高いからである。

0044

選択部113bは、類似度算出部113aによって算出された類似度に基づいて、最も類似度の高い部分命令列122の組合せを選択する。組合せパターン生成部113cは、選択部113bによって選択された組合せに含まれる分割当初の部分命令列122を組み合わせて複数の組合せパターン123を生成する。組合せパターン123の具体的な生成方法は、既に図6図7を用いて説明した通りであり、組合せパターン123は、図6に示したP−4−5およびP−5−4や、図7に示したP−7−5−4、P−5−7−4およびP−5−4−7に相当する。

0045

尤度算出部113dは、組合せパターン生成部113cによって生成された各組合せパターン123の尤度を算出する。尤度は、組合せパターン123に含まれる命令を先頭から順に前後で比較し、比較結果を尤度得点データ125と照合して得られた得点(命令単位の尤度)を合計することにより算出される。

0046

尤度得点データ125の一例を図10に示す。図10に示すように、尤度得点データ125には、関数名が一致した場合の得点として「10」が設定され、関数名が不一致であった場合の得点として、それよりも低い「0」が設定されている。また、関数名が一致した場合に関数内オフセットの差分に基づいて与えられる得点として、差分が正であり、かつ、差分の大きさが「1」に近いほど高い値が設定されている。なお、ここでは、後の命令の関数内オフセットから前の命令の関数内オフセットを減算することによって関数内オフセットの差分を算出することを前提としており、差分が正であるということは、関数内オフセットが昇順に並んでいることを意味する。

0047

部分命令列置換部113eは、尤度算出部113dによって算出された尤度に基づいて、複数の組合せパターン123の中から尤度が最も高いものを選択する。そして、部分命令列置換部113eは、選択した組合せパターン123を、選択部113bによって選択された組合せに含まれる部分命令列122に代えて、部分命令列122として記憶部120に記憶させる。なお、部分命令列置換部113eによって選択された組合せパターン123が部分命令列122として記憶部120に記憶された後、他の組合せパターン123は削除される。

0048

なお、ここでは、部分命令列置換部113eが選択した組合せパターン123を、選択部113bによって選択された組合せに含まれる部分命令列122に代えて、部分命令列122として記憶部120に記憶させることとしたが、この通りである必要はない。具体的には、以降の処理において、選択部113bによって選択された組合せに含まれる部分命令列122の代わりに、尤度が最も高い組合せパターン123が使用されるようになればよい。

0049

命令トレース出力部114は、合成制御部113の制御によって部分命令列122が1つの命令列に合成された後に、合成後の命令列を命令トレースとして出力する。

0050

記憶部120は、各種情報を記憶する記憶デバイスであり、サンプリングデータ121と、部分命令列122と、組合せパターン123と、類似度得点データ124と、尤度得点データ125とを記憶する。なお、記憶部120が記憶する各種データについては、既に説明済みであるため、ここでは説明を省略する。

0051

次に、図8に示した命令トレース生成装置100の動作について説明する。図11は、命令トレース生成装置100による命令トレース生成処理処理手順を示すフローチャートである。

0052

命令トレース生成処理においては、まず、命令情報設定部111が、予め採取されたサンプリングデータ121に含まれる各命令に、関数名と関数内オフセットを命令情報として設定する(ステップS101)。そして、分割部112が、サンプリングデータ121を部分命令列122に分割し、部分命令列122を記憶部120に記憶させる(ステップS102)。

0053

ここで、記憶部120に記憶されている部分命令列122が1つでなければ(ステップS103否定)、類似度算出部113aが、部分命令列122の組合せを全て生成する(ステップS104)。そして、類似度算出部113aは、生成された組合せのうち、未選択のものを1つ選択し(ステップS105)、選択できた場合は(ステップS106否定)、選択した組合せに対して後述する類似度算出処理を実行して類似度を算出する(ステップS107)。

0054

そして、類似度算出処理が完了した後、類似度算出部113aは、ステップS105に戻って、次の未選択の組合せの取得を試みる。こうして、全ての組合せが選択済みとなり、全ての組合せの類似度の算出が完了すると(ステップS106肯定)、選択部113bが、類似度の最も高い部分命令列122の組合せを選択する(ステップS108)。

0055

続いて、組合せパターン生成部113cが、選択された部分命令列122の組合せから複数の組合せパターン123を生成する(ステップS109)。そして、尤度算出部113dが、生成された組合せパターン123のうち、未選択のものを1つ選択し(ステップS110)、選択できた場合は(ステップS111否定)、選択した組合せパターン123に対して後述する尤度算出処理を実行して尤度を算出する(ステップS112)。

0056

そして、尤度算出処理が完了した後、尤度算出部113dは、ステップS110に戻って、次の未選択の組合せパターン123の取得を試みる。こうして、全ての組合せパターン123選択済みとなり、全ての組合せパターン123の尤度の算出が完了する。すると(ステップS111肯定)、部分命令列置換部113eが、尤度の最も高い組合せパターン123を、合成前の部分命令列122に代えて、部分命令列122として記憶部120に記憶させる(ステップS113)。そして、部分命令列置換部113eの処理が完了した後、ステップS103以降が再実行される。

0057

こうして、ステップS103〜ステップS113が繰り返し実行されて、部分命令列122が1つに合成される。すると(ステップS103肯定)、命令トレース出力部114が、1つに合成された部分命令列122からステップS101で設定された命令情報を削除する等の加工を行って、命令トレースを生成する(ステップS114)。そして、命令トレース出力部114は、生成された命令トレースを出力する(ステップS115)。

0058

図12は、ステップS107の類似度算出処理の処理手順を示すフローチャートである。類似度算出処理において、類似度算出部113aは、まず、類似度を0に設定する(ステップS201)。そして、類似度算出部113aは、類似度の算出対象の一方の部分命令列122から未取得の命令情報のうち先頭のものを取得する(ステップS202)。ここで、その部分命令列122の全ての命令情報を既に取得済であった場合(ステップS203肯定)、類似度算出部113aは、類似度算出処理を終了する。

0059

一方、命令情報を取得できた場合(ステップS203否定)、類似度算出部113aは、類似度の算出対象のもう一方の部分命令列122から未取得の命令情報のうち先頭のものを取得する(ステップS204)。ここで、その部分命令列122の全ての命令情報を既に取得済であった場合(ステップS205肯定)、類似度算出部113aは、類似度算出処理を終了する。

0060

もう一方の部分命令列122からも命令情報を取得できた場合(ステップS205否定)、類似度算出部113aは、取得された命令情報に含まれる関数名を比較する(ステップS206)。そして、関数名が一致しなかった場合(ステップS207否定)、類似度算出部113aは、類似度得点データ124から、関数名不一致時の点数を取得して類似度に加算し(ステップS208)、ステップS202から処理を再開する。

0061

関数名が一致した場合(ステップS207肯定)、類似度算出部113aは、類似度得点データ124から、関数名一致時の点数を取得して類似度に加算する(ステップS209)。さらに、類似度算出部113aは、取得された命令情報に含まれる関数内オフセットの差分を算出する(ステップS210)。そして、類似度算出部113aは、類似度得点データ124から、算出された差分に対応する点数を取得して類似度に加算し(ステップS211)、ステップS202から処理を再開する。

0062

図13は、尤度算出処理の処理手順を示すフローチャートである。尤度算出処理において、尤度算出部113dは、まず、尤度を0に設定する(ステップS301)。そして、尤度算出部113dは、尤度の算出対象の組合せパターン123から先頭の命令情報を取得する(ステップS302)。

0063

そして、尤度算出部113dは、尤度の算出対象の組合せパターン123から次の命令情報を取得する(ステップS303)。ここで、その組合せパターン123の全ての命令情報を既に取得済であった場合(ステップS304肯定)、尤度算出部113dは、尤度算出処理を終了する。

0064

組合せパターン123から次の命令情報を取得できた場合(ステップS304否定)、尤度算出部113dは、今回取得された命令情報に含まれる関数名を直前に取得された命令情報に含まれる関数名と比較する(ステップS305)。そして、関数名が一致しなかった場合(ステップS306否定)、尤度算出部113dは、尤度得点データ125から、関数名不一致時の点数を取得して尤度に加算し(ステップS307)、ステップS303から処理を再開する。

0065

関数名が一致した場合(ステップS306肯定)、尤度算出部113dは、尤度得点データ125から、関数名一致時の点数を取得して尤度に加算する(ステップS308)。さらに、尤度算出部113dは、今回取得された命令情報に含まれる関数内オフセットから直前に取得された命令情報に含まれる関数内オフセットを減算して差分を算出する(ステップS309)。そして、尤度算出部113dは、尤度得点データ125から、算出された差分に対応する点数を取得して尤度に加算し(ステップS310)、ステップS303から処理を再開する。

0066

上述してきたように、本実施例では、プロセッサによって実行された命令を、所定の間隔でサンプリングして得られたサンプリングデータを部分命令列に分割し、類似度と尤度に基づいて合成することとしたので、実行中のプログラムの挙動に影響がない程度に情報を取得する頻度を下げつつ、所望する命令トレースを取得することができる。

0067

なお、上述した例では、所定数間隔で命令をサンプリングして得られたサンプリングデータから命令トレースを生成する例を示したが、本実施例に係る命令トレース方法は、所定時間間隔で命令をサンプリングして得られたサンプリングデータに対しても適用することができる。所定時間間隔で命令をサンプリングして得られたサンプリングデータに対して本実施例に係る命令トレース方法を適用した場合、得られ命令トレースは、実行時間重み付き命令トレースとなる。

0068

図14は、実行時間重み付き命令トレースの生成の一例を示す図である。命令列12は、図1に示したプログラムを動作させた場合の通常の命令トレースに相当する命令列であり、サンプリングデータ22は、プロセッサによって実行された命令を所定時間間隔でサンプリングして得られた命令列である。プロセッサによって実行される命令の実行時間は、命令の種類等によって異なるため、サンプリングデータ22には、各命令の実行時間の長短が反映される。

0069

このようなサンプリングデータ22を、本実施例に係る命令トレース方法を用いて合成することにより、実行時間重み付き命令トレース32が得られる。実行時間重み付き命令トレース32では、同一の命令が連続する数によってその命令の実行時間が示される。このような実行時間重み付き命令トレースを生成することにより、命令の実行順序だけでなく、命令の実行時間まで知ることが可能になり、プログラムの最適化等に非常に有効な情報を得ることができる。

0070

なお、実行時間重み付き命令トレースを生成する場合は、同一の命令が連続して命令列に出現することが通常であるため、関数内オフセットの差分が0のときに最も得点が高くなるように類度得点データ124と尤度得点データ125を設定する必要がある。

0071

実施例1では、関数名と関数内オフセットに基づいて部分命令列を合成する例を示したが、ベーシックブロック(以下「BB」という)を考慮することによって、生成される命令トレースの精度をさらに向上させることができる。BBとは、分岐命令によって区切られた命令のブロックであり、関数よりも細かい単位である。

0072

図15は、BBを考慮した命令トレースの生成の一例を示す図である。本実施例において各命令に付与されている文字列の最初の「:」よりも前の部分は、その命令が属している関数の名称を表す。最初の「:」と2番目の「:」の間の部分は、その命令が属しているBBの関数内での出現順序(以下「BB番号」という)を表す。そして、2番目の「:」よりも後ろの部分は、BBの先頭を基準とした場合のその命令のオフセット(以下「BB内オフセット」という)を表わす。例えば、「func_A:BB1:0」は、func_A()という名前の関数において1番目に出現するBBの先頭の命令であることを示す。

0073

図1に示したプログラムにおいて、func_A()は、4つの命令を有する第1のBBと、3つの命令を有する第2のBBと、3つの命令を有する第3のBBとからなるものとする。また、func_B()は、3つの命令を有する第1のBBと、7つの命令を有する第2のBBとからなり、func_C()は、10個の命令を有する1つのBBからなるものとする。

0074

この場合、図1に示したプログラムを動作させると、図15に示した命令列13がプロセッサによって実行される。そして、プロセッサによって実行される命令を7個毎にサンプリングすると、サンプリングデータ23が得られる。こうして得られたサンプリングデータ23は、命令トレースの取得対象であるfunc_M()が1回呼び出された間に取得された単位で部分命令列に分割される。

0075

そして、関数名と、BB番号と、BB内オフセットとに基づいて類似度と尤度を算出しながら部分命令列を合成していくことにより、命令トレース33を得ることができる。こうして得られた命令トレース33は、関数よりも細かい単位であるBBを考慮して合成されたものであるため、実際にプロセッサによって実行された順番通りに正確に命令が配置されていることが期待される。

0076

次に、本実施例に係る命令トレース生成方法を実行する命令トレース生成装置の構成について説明する。図16は、本実施例に係る命令トレース生成装置200の構成を示す機能ブロック図である。図16に示すように、命令トレース生成装置200は、制御部210と、記憶部220とを有する。なお、以下の説明では、既に説明した部位と同一の部位には、既に説明した部位と同一の符号を付して、重複する説明を省略することとする。

0077

制御部210は、命令トレース生成装置200を全体制御する制御部である。制御部210は、命令情報設定部211と、分割部112と、合成制御部113と、類似度算出部213aと、選択部113bと、組合せパターン生成部113cと、尤度算出部213dと、部分命令列置換部113eと、命令トレース出力部114とを有する。

0078

命令情報設定部211は、記憶部220に記憶されているサンプリングデータ221に対して命令情報を設定する。サンプリングデータ221は、命令トレースの取得対象の命令列を複数回実行している間にプロセッサによって実行された命令を所定間隔でサンプリングして得られたデータであり、命令トレースを生成するために十分な数の命令を含んでいる。

0079

具体的には、命令情報設定部211は、サンプリングデータ221に含まれる命令毎に、関数名と、BB番号と、BB内オフセットを命令情報として設定する。なお、関数名は、例えば、命令のアドレスをプログラム中のシンボルテーブルと照合することによって取得することができる。また、BB番号とBB内オフセットは、例えば、命令のアドレスをプログラム中のシンボルテーブルと照合することによって得られた関数の先頭のアドレスを基準として、プログラム中の命令列を解析することにより取得することができる。

0080

類似度算出部213aは、分割部112がサンプリングデータ221を分割することによって得られた部分命令列222の組合せの全てについて類似度を算出する。類似度は、各部分命令列222に含まれる命令を先頭から順に比較し、比較結果を類似度得点データ224と照合して得られた得点(命令単位の類似度)を合計することにより算出される。

0081

類似度得点データ224の一例を図17に示す。図17に示すように、類似度得点データ124には、関数名が一致した場合の得点として「5」が設定され、関数名が不一致であった場合の得点として、それよりも低い「0」が設定されている。また、関数名が一致した場合にBB番号の差分に基づいて与えられる得点として、差分が「0」に近いほど高い値が設定されている。また、BB番号の差分が0であった場合、すなわち、BB番号が一致した場合にBB内オフセットの差分に基づいて与えられる得点として、差分の絶対値が「1」に近いほど高い値が設定されている。

0082

尤度算出部213dは、組合せパターン生成部113cによって生成された各組合せパターン223の尤度を算出する。尤度は、組合せパターン223に含まれる命令を先頭から順に前後で比較し、比較結果を尤度得点データ225と照合して得られた得点(命令単位の尤度)を合計することにより算出される。

0083

尤度得点データ225の一例を図18に示す。図18に示すように、尤度得点データ225には、関数名が一致した場合の得点として「5」が設定され、関数名が不一致であった場合の得点として、それよりも低い「0」が設定されている。また、関数名が一致した場合にBB番号の差分に基づいて与えられる得点として、差分が「0」に近いほど高い値が設定されている。また、BB番号の差分が0であった場合、すなわち、BB番号が一致した場合にBB内オフセットの差分に基づいて与えられる得点として、差分が正であり、かつ、差分の絶対値が「1」に近いほど高い値が設定されている。

0084

記憶部220は、各種情報を記憶する記憶デバイスであり、サンプリングデータ221と、部分命令列222と、組合せパターン223と、類似度得点データ224と、尤度得点データ225とを記憶する。なお、記憶部220が記憶する各種データについては、既に説明済みであるため、ここでは説明を省略する。

0085

次に、図16に示した命令トレース生成装置200の動作について説明する。図19は、命令トレース生成装置200による命令トレース生成処理の処理手順を示すフローチャートである。

0086

命令トレース生成処理においては、まず、命令情報設定部211が、予め採取されたサンプリングデータ221に含まれる各命令に、関数名と、BB番号と、BB内オフセットを命令情報として設定する(ステップS401)。その後の処理については、ステップS407の類似度算出処理と、ステップS412の尤度算出処理を除いて、図11に示した処理手順と同様である。

0087

図20は、類似度算出処理の処理手順を示すフローチャートである。類似度算出処理において、類似度算出部213aは、まず、類似度を0に設定する(ステップS501)。そして、類似度算出部213aは、類似度の算出対象の一方の部分命令列222から未取得の命令情報のうち先頭のものを取得する(ステップS502)。ここで、その部分命令列222の全ての命令情報を既に取得済であった場合(ステップS503肯定)、類似度算出部213aは、類似度算出処理を終了する。

0088

一方、命令情報を取得できた場合(ステップS503否定)、類似度算出部213aは、類似度の算出対象のもう一方の部分命令列222から未取得の命令情報のうち先頭のものを取得する(ステップS504)。ここで、その部分命令列222の全ての命令情報を既に取得済であった場合(ステップS505肯定)、類似度算出部213aは、類似度算出処理を終了する。

0089

もう一方の部分命令列222からも命令情報を取得できた場合(ステップS505否定)、類似度算出部213aは、取得された命令情報に含まれる関数名を比較する(ステップS506)。そして、関数名が一致しなかった場合(ステップS507否定)、類似度算出部213aは、類似度得点データ224から、関数名不一致時の点数を取得して類似度に加算し(ステップS508)、ステップS502から処理を再開する。

0090

関数名が一致した場合(ステップS507肯定)、類似度算出部213aは、類似度得点データ224から、関数名一致時の点数を取得して類似度に加算する(ステップS509)。そして、類似度算出部213aは、取得された命令情報に含まれるBB番号を比較する(ステップS510)。ここで、BB番号が一致しなかった場合(ステップS511否定)、類似度算出部213aは、BB番号の差分を算出する(ステップS512)。そして、類似度算出部213aは、類似度得点データ224から、算出されたBB番号の差分に対応する点数を取得して類似度に加算し(ステップS513)、ステップS502から処理を再開する。

0091

一方、BB番号が一致した場合(ステップS511肯定)、類似度算出部213aは、類似度得点データ224から、BB番号一致時の点数を取得して類似度に加算する(ステップS514)。さらに、類似度算出部213aは、取得された命令情報に含まれるBB内オフセットの差分を算出する(ステップS515)。そして、類似度算出部213aは、類似度得点データ224から、算出されたBB内オフセットの差分に対応する点数を取得して類似度に加算し(ステップS516)、ステップS502から処理を再開する。

0092

図21は、尤度算出処理の処理手順を示すフローチャートである。尤度算出処理において、尤度算出部213dは、まず、尤度を0に設定する(ステップS601)。そして、尤度算出部213dは、尤度の算出対象の組合せパターン223から先頭の命令情報を取得する(ステップS602)。

0093

そして、尤度算出部213dは、尤度の算出対象の組合せパターン223から次の命令情報を取得する(ステップS603)。ここで、その組合せパターン223の全ての命令情報を既に取得済であった場合(ステップS604肯定)、尤度算出部213dは、尤度算出処理を終了する。

0094

組合せパターン223から次の命令情報を取得できた場合(ステップS604否定)、尤度算出部213dは、今回取得された命令情報に含まれる関数名を直前に取得された命令情報に含まれる関数名と比較する(ステップS605)。そして、関数名が一致しなかった場合(ステップS606否定)、尤度算出部213dは、尤度得点データ225から、関数名不一致時の点数を取得して尤度に加算し(ステップS607)、ステップS603から処理を再開する。

0095

関数名が一致した場合(ステップS606肯定)、尤度算出部213dは、尤度得点データ225から、関数名一致時の点数を取得して尤度に加算する(ステップS608)。そして、尤度算出部213dは、取得された命令情報に含まれるBB番号を直前に取得された命令情報に含まれるBB番号比較する(ステップS609)。ここで、BB番号が一致しなかった場合(ステップS610否定)、尤度算出部213dは、BB番号の差分を算出する(ステップS611)。そして、尤度算出部213dは、尤度得点データ225から、算出されたBB番号の差分に対応する点数を取得して尤度に加算し(ステップS612)、ステップS603から処理を再開する。

0096

一方、BB番号が一致した場合(ステップS610肯定)、尤度算出部213dは、尤度得点データ225から、BB番号一致時の点数を取得して類似度に加算する(ステップS613)。さらに、尤度算出部213dは、今回取得された命令情報に含まれるBB内オフセットから直前に取得された命令情報に含まれるBB内オフセットを減算して差分を算出する(ステップS614)。そして、尤度算出部213dは、尤度得点データ225から、算出された差分に対応する点数を取得して尤度に加算し(ステップS615)、ステップS603から処理を再開する。

0097

上述してきたように、本実施例では、BBを考慮して部分命令列を合成することとしたので、正確な命令トレースを生成することができる。

0098

なお、実施例1に係る命令トレース生成装置100や実施例2に係る命令トレース生成装置200の構成は、要旨を逸脱しない範囲で種々に変更することができる。例えば、命令トレース生成装置100の制御部110の機能や命令トレース生成装置200の制御部210の機能をソフトウェアとして実装し、これをコンピュータで実行することにより、命令トレース生成装置100や命令トレース生成装置200と同等の機能を実現することもできる。以下に、制御部110の機能をソフトウェアとして実装した命令トレース生成プログラム1071を実行するコンピュータの一例を示す。

0099

図22は、命令トレース生成プログラム1071を実行するコンピュータ1000を示す機能ブロック図である。このコンピュータ1000は、各種演算処理を実行するCPU(Central Processing Unit)1010と、ユーザからのデータの入力を受け付け入力装置1020と、各種情報を表示するモニタ1030と、記録媒体からプログラム等を読み取る媒体読取り装置1040と、ネットワークを介して他のコンピュータとの間でデータの授受を行うネットワークインターフェース装置1050と、各種情報を一時記憶するRAM(Random Access Memory)1060と、ハードディスク装置1070とをバス1080で接続して構成される。

0100

そして、ハードディスク装置1070には、図8に示した制御部110と同様の機能を有する命令トレース生成プログラム1071と、図8に示した記憶部120に記憶される各種データに対応する命令トレース生成用データ1072とが記憶される。なお、命令トレース生成用データ1072を、適宜分散させ、ネットワークを介して接続された他のコンピュータに記憶させておくこともできる。

0101

そして、CPU1010が命令トレース生成プログラム1071をハードディスク装置1070から読み出してRAM1060に展開することにより、命令トレース生成プログラム1071は、命令トレース生成プロセス1061として機能するようになる。そして、命令トレース生成プロセス1061は、命令トレース生成用データ1072から読み出した情報等を適宜RAM1060上の自身に割り当てられた領域に展開し、この展開したデータ等に基づいて各種データ処理を実行する。そして、命令トレース生成プロセス1061は、各種データ処理によって生成された命令トレースデータ1073をハードディスク装置1070に記憶させる。

0102

なお、上記の命令トレース生成プログラム1071は、必ずしもハードディスク装置1070に格納されている必要はなく、CD−ROM等の記憶媒体に記憶されたこのプログラムを、コンピュータ1000が読み出して実行するようにしてもよい。また、公衆回線インターネット、LAN(Local Area Network)、WAN(Wide Area Network)等を介してコンピュータ1000に接続される他のコンピュータ(またはサーバ)等にこのプログラムを記憶させておき、コンピュータ1000がこれらからプログラムを読み出して実行するようにしてもよい。

0103

以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。

0104

(付記1)複数回実行される第1の命令列を所定間隔でサンプリングして得られた第2の命令列から、該第1の命令列の命令トレースを生成する命令トレース生成プログラムであって、
前記第2の命令列を、部分命令列に分割し、分割された各部分命令列を記憶手段に記憶させる分割手順と、
前記記憶手段に記憶された全ての部分命令列の組合せ毎に類似度を算出する類似度算出手順と、
前記類似度算出手順によって算出された類似度に基づいて部分命令列の組合せを選択する選択手順と、
前記選択手順によって選択された部分命令列に含まれる命令を組み合わせて複数の組合せパターンを生成する組合せパターン生成手順と、
前記組合せパターン生成手順によって生成された組合せパターン毎に尤度を算出する尤度算出手順と、
前記尤度算出手順によって算出された尤度に基づいて組合せパターンを前記記憶手段に記憶させる部分命令列置換手順と
をコンピュータに実行させることを特徴とする命令トレース生成プログラム。

0105

(付記2)合成制御手順をコンピュータにさらに実行させ、
前記選択手順は、前記類似度算出手順によって算出された類似度が最も高い部分命令列の組合せを選択し、
前記部分命令列置換手順は、前記尤度算出手順によって算出された尤度が最も高い組合せパターンを、前記選択手順によって選択された部分文字列に代えて、部分文字列として前記記憶手段に記憶させ、
前記合成制御手順は、前記記憶手段に記憶される部分命令列が1つになるまで、前記類似度算出手順と、前記選択手順と、前記組合せパターン生成手順と、前記部分命令列置換手順とを制御することを特徴とする付記1に記載の命令トレース生成プログラム。

0106

(付記3)前記類似度算出手順は、部分命令列に含まれる命令が属する関数の関数名と、該関数の先頭からの該命令のオフセットとに基づいて類似度を算出することを特徴とする付記1または2に記載の命令トレース生成プログラム。

0107

(付記4)前記尤度算出手順は、部分命令列に含まれる命令が属する関数の関数名と、該関数の先頭からの該命令のオフセットとに基づいて尤度を算出することを特徴とする付記1から3のいずれか1つに記載の命令トレース生成プログラム。

0108

(付記5)前記類似度算出手順は、部分命令列に含まれる命令が属する関数の関数名と、該命令が含まれるベーシックブロックと、該ベーシックブロックの先頭からの該命令のオフセットとに基づいて類似度を算出することを特徴とする付記1に記載の命令トレース生成プログラム。

0109

(付記6)前記尤度算出手順は、部分命令列に含まれる命令が属する関数の関数名と、該命令が含まれるベーシックブロックと、該ベーシックブロックの先頭からの該命令のオフセットとに基づいて尤度を算出することを特徴とする付記1に記載の命令トレース生成プログラム。

0110

(付記7)複数回実行される第1の命令列を所定間隔でサンプリングして得られた第2の命令列から、該第1の命令列の命令トレースを生成する命令トレース生成装置であって、
前記第2の命令列を、部分命令列に分割し、分割された各部分命令列を記憶手段に記憶させる分割手段と、
前記記憶手段に記憶された全ての部分命令列の組合せ毎に類似度を算出する類似度算出手段と、
前記類似度算出手段によって算出された類似度に基づいて部分命令列の組合せを選択する選択手段と、
前記選択手段によって選択された部分命令列に含まれる命令を組み合わせて複数の組合せパターンを生成する組合せパターン生成手段と、
前記組合せパターン生成手段によって生成された組合せパターン毎に尤度を算出する尤度算出手段と、
前記尤度算出手段によって算出された尤度に基づいて組合せパターンを前記記憶手段に記憶させる部分命令列置換手段と
を備えることを特徴とする命令トレース生成装置。

0111

(付記8)合成制御手段をさらに備え、
前記選択手段は、前記類似度算出手段によって算出された類似度が最も高い部分命令列の組合せを選択し、
前記部分命令列置換手段は、前記尤度算出手段によって算出された尤度が最も高い組合せパターンを、前記選択手段によって選択された部分文字列に代えて、部分文字列として前記記憶手段に記憶させ、
前記合成制御手段は、前記記憶手段に記憶される部分命令列が1つになるまで、前記類似度算出手段と、前記選択手段と、前記組合せパターン生成手段と、前記部分命令列置換手段とを制御することを特徴とする付記7に記載の命令トレース生成装置。

0112

(付記9)前記類似度算出手段は、部分命令列に含まれる命令が属する関数の関数名と、該関数の先頭からの該命令のオフセットとに基づいて類似度を算出することを特徴とする付記7または8に記載の命令トレース生成装置。

0113

(付記10)前記尤度算出手段は、部分命令列に含まれる命令が属する関数の関数名と、該関数の先頭からの該命令のオフセットとに基づいて尤度を算出することを特徴とする付記7〜9のいずれか1つに記載の命令トレース生成装置。

0114

(付記11)前記類似度算出手段は、部分命令列に含まれる命令が属する関数の関数名と、該命令が含まれるベーシックブロックと、該ベーシックブロックの先頭からの該命令のオフセットとに基づいて類似度を算出することを特徴とする付記7に記載の命令トレース生成装置。

0115

(付記12)前記尤度算出手段は、部分命令列に含まれる命令が属する関数の関数名と、該命令が含まれるベーシックブロックと、該ベーシックブロックの先頭からの該命令のオフセットとに基づいて尤度を算出することを特徴とする付記7に記載の命令トレース生成装置。

0116

(付記13)複数回実行される第1の命令列を所定間隔でサンプリングして得られた第2の命令列から、該第1の命令列の命令トレースを生成する命令トレース生成方法であって、
前記第2の命令列を、部分命令列に分割し、分割された各部分命令列を記憶手段に記憶させる分割工程と、
前記記憶手段に記憶された全ての部分命令列の組合せ毎に類似度を算出する類似度算出工程と、
前記類似度算出工程によって算出された類似度に基づいて部分命令列の組合せを選択する選択工程と、
前記選択工程によって選択された部分命令列に含まれる命令を組み合わせて複数の組合せパターンを生成する組合せパターン生成工程と、
前記組合せパターン生成工程によって生成された組合せパターン毎に尤度を算出する尤度算出工程と、
前記尤度算出工程によって算出された尤度に基づいて組合せパターンを前記記憶手段に記憶させる部分命令列置換工程と
を含むことを特徴とする命令トレース生成方法。

0117

(付記14)合成制御工程をさらに備え、
前記選択工程は、前記類似度算出工程によって算出された類似度が最も高い部分命令列の組合せを選択し、
前記部分命令列置換工程は、前記尤度算出工程によって算出された尤度が最も高い組合せパターンを、前記選択工程によって選択された部分文字列に代えて、部分文字列として前記記憶手段に記憶させ、
前記合成制御工程は、前記記憶手段に記憶される部分命令列が1つになるまで、前記類似度算出工程と、前記選択工程と、前記組合せパターン生成工程と、前記部分命令列置換工程とを制御することを特徴とする付記13に記載の命令トレース生成方法。

0118

(付記15)前記類似度算出工程は、部分命令列に含まれる命令が属する関数の関数名と、該関数の先頭からの該命令のオフセットとに基づいて類似度を算出することを特徴とする付記13または14に記載の命令トレース生成方法。

0119

(付記16)前記類似度算出工程は、部分命令列に含まれる命令が属する関数の関数名と、該命令が含まれるベーシックブロックと、該ベーシックブロックの先頭からの該命令のオフセットとに基づいて類似度を算出することを特徴とする付記13〜15のいずれか1つに記載の命令トレース生成方法。

0120

(付記17)前記尤度算出工程は、部分命令列に含まれる命令が属する関数の関数名と、該関数の先頭からの該命令のオフセットとに基づいて尤度を算出することを特徴とする付記13に記載の命令トレース生成方法。

0121

(付記18)前記尤度算出工程は、部分命令列に含まれる命令が属する関数の関数名と、該命令が含まれるベーシックブロックと、該ベーシックブロックの先頭からの該命令のオフセットとに基づいて尤度を算出することを特徴とする付記13に記載の命令トレース生成方法。

図面の簡単な説明

0122

プログラムの一例を示す図である。
命令のサンプリングの一例を示す図である。
サンプリングデータの一例を示す図である。
部分命令列の一例を示す図である。
類似度の算出結果の一例を示す図である。
部分命令列の合成の一例を示す図である。
部分命令列の合成の他の一例を示す図である。
実施例1に係る命令トレース生成装置の構成を示す機能ブロック図である。
類似度得点データのデータ構成の一例を示す図である。
尤度得点データのデータ構成の一例を示す図である。
命令トレース生成処理の処理手順を示すフローチャートである。
類似度算出処理の処理手順を示すフローチャートである。
尤度算出処理の処理手順を示すフローチャートである。
実行時間重み付き命令トレースの生成の一例を示す図である。
ベーシックブロックを考慮した命令トレースの生成の一例を示す図である。
実施例2に係る命令トレース生成装置の構成を示す機能ブロック図である。
類似度得点データのデータ構成の一例を示す図である。
尤度得点データのデータ構成の一例を示す図である。
命令トレース生成処理の処理手順を示すフローチャートである。
類似度算出処理の処理手順を示すフローチャートである。
尤度算出処理の処理手順を示すフローチャートである。
命令トレース生成プログラムを実行するコンピュータを示す機能ブロック図である。

符号の説明

0123

11〜13命令列
21〜23サンプリングデータ
32 実行時間重み付き命令トレース
33 命令トレース
100、200命令トレース生成装置
110、210 制御部
111、211命令情報設定部
112 分割部
113 合成制御部
113a、213a類似度算出部
113b 選択部
113c組合せパターン生成部
113d、213d尤度算出部
113e部分命令列置換部
114 命令トレース出力部
120、220 記憶部
121、221 サンプリングデータ
122、222 部分命令列
123、223 組合せパターン
124、224類似度得点データ
125、225尤度得点データ
1000コンピュータ
1010 CPU
1020入力装置
1030モニタ
1040媒体読取り装置
1050ネットワークインターフェース装置
1060 RAM
1061 命令トレース生成プロセス
1070ハードディスク装置
1071 命令トレース生成プログラム
1072 命令トレース生成用データ
1073命令トレースデータ
1080 バス

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ