WEKO3
アイテム
{"_buckets": {"deposit": "4f122bd1-37dd-4b8d-b6b1-ef9bd201205e"}, "_deposit": {"created_by": 3, "id": "1244", "owners": [3], "pid": {"revision_id": 0, "type": "depid", "value": "1244"}, "status": "published"}, "_oai": {"id": "oai:uec.repo.nii.ac.jp:00001244", "sets": ["12"]}, "author_link": ["7292"], "control_number": "1244", "item_10006_date_granted_11": {"attribute_name": "学位授与年月日", "attribute_value_mlt": [{"subitem_dategranted": "2006-03-23"}]}, "item_10006_degree_grantor_9": {"attribute_name": "学位授与機関", "attribute_value_mlt": [{"subitem_degreegrantor": [{"subitem_degreegrantor_name": "電気通信大学"}]}]}, "item_10006_degree_name_8": {"attribute_name": "学位名", "attribute_value_mlt": [{"subitem_degreename": "博士(工学)"}]}, "item_10006_description_10": {"attribute_name": "学位授与年度", "attribute_value_mlt": [{"subitem_description": "2006", "subitem_description_type": "Other"}]}, "item_10006_description_7": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "本研究では,言語処理系の実装に関連する二つの事項を取り扱う.本論文の第1 部(第2 章~第4章)では,実行時系における記憶場所の動的な管理である「ごみ集め」に関して議論する.ごみ集めは,記号処理言語やオブジェクト指向型言語の実装には不可欠なしくみで,その性能が全体の性能を左右する.そして,第2 部(第5 章~第8 章)では,SIMD(Single Instruction Multiple Data-stream)命令の一種のレジスタ分割型ショートベクタ命令セット(以下SIMD 命令と略す)に注目し,翻訳系によるSIMD 命令向け最適化に関して議論する.この命令セットは,メディアデータ処理の高速化の安価な手法として考案され定着してきた.これには,従来のコード最適化技法を応用可能な事項もあるが,新しく開発する必要がある事項も多い.現状では,コンパイラによるSIMD 命令の自動生成は研究段階であるので,アセンブリ言語等を用いないとSIMD 命令の満足がいく活用ができない.第1 章では,二つの事項を研究するに至る背景について議論する.第2 章では,先ず,第1 部で取り扱うごみ集め問題を定式化した.次に,参照計数法,複写法,印掃法というごみ集めの三つの戦略を示した.そして,従来の印掃法のごみ集めでは解決されていなかった二つの問題を指摘し,関連する既存の成果を紹介し分析した.第3 章で議論している第一の問題は,印掃法ごみ集めの実行時間を小さくすることである.従来の印掃法ごみ集めは,記憶領域のサイズをS として,S に比例する時間が必要であった.これに対し,使用中の記憶の量をA として,理論上の計算量はAlogA,実用上はA に比例する実行時間で済む印掃法のごみ集めで,使用領域を圧縮するもの(以下印掃式圧縮型と略す)を提案した.これにより,A がS の1割以下という一般的な状況の下では,ごみ集めが高速化された.第4 章で議論している第二の問題は,「世代別ごみ集め」と呼ばれるごみ集めの手間を省く戦略を,印掃法の圧縮型ごみ集めに適用することである.世代別ごみ集めは,通常は,複写法のごみ集めとの組み合わせで実現される.ここでは,印掃法の圧縮型ごみ集めの生成順序保存という特徴を生かした方法を提案し,小さなオーバヘッドで世代別ごみ集めを実装する方法を示した.これにより,さらにごみ集めが高速化された.第5 章では,先ず,第2 部で取り扱うSIMD 命令の動作や種類を説明する.次に,コンパイラによるSIMD 命令の自動生成に関する問題点を指摘し,関連する既存の成果を紹介し分析する.そして,本研究での実装に関連する成果を紹介する.第6 章で議論している第一の問題は,SIMD 命令向けの言語仕様の拡張を使用していない(つまり通常の言語規格の範囲内で記述された)プログラムから,SIMD 命令の振る舞いに相当するオペレーションを抽出する方法である.このために,覗き穴最適化を応用した方法による最適化技法を提案した.第7 章で議論している第二の問題は,高級言語の汎整数拡張が,効果的なSIMD 命令の適用を阻害していることである.汎整数拡張とは,汎整数型(通常は計算機が効率よく処理できる整数型)より小さいサイズのデータは,演算に使用される前に汎整数型への符号拡張やゼロ拡張が施されるという仕様である.これに対して,なるべく小さいデータサイズによる演算で,汎整数拡張を行う場合と同じ結果を得るためのプログラム解析法を提案した.第8 章で議論している第三の問題は,実在する多くのベクタ処理向きのプログラムやベンチマークプログラムが,コンパイラによるSIMD 命令活用のベンチマークに適していないことである.そこで,これらの中の例題を分析し,SIMD 命令を効果的に適用できるように変形し,SIMD 命令向きのコーディングを示した.さらに,コンパイラのSIMD 命令の活用度を調べるためのベンチマークとして,各々の例題に対して,SIMD 命令の適用を容易にする種々の変形を組織的に施したプログラム集で,複数の変形版から成るものを用意した.最後に第9 章では,本研究で得られた成果を総括する.成果の一つは,記憶領域の使用効率が高く,実行時間も小さいごみ集めを提案したことである.それにより,記憶領域が乏しい計算機でも,近代的な言語が必須とするごみ集めを効率よく実現できる.もう一つは,SIMD 命令向けの最適化技術を提案し,実装し,評価し,実行性能の向上を示したことである.これにより,命令セットが異なる計算機間でも,同じメディアデータ処理プログラムを共有できるようになる.", "subitem_description_type": "Abstract"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "鈴木, 貢", "creatorNameLang": "ja"}, {"creatorName": "スズキ, ミツグ", "creatorNameLang": "ja-Kana"}, {"creatorName": "Suzuki, Mitsugu", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "7292", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2016-09-16"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "9000000121.pdf", "filesize": [{"value": "756.6 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 756600.0, "url": {"label": "9000000121.pdf", "url": "https://uec.repo.nii.ac.jp/record/1244/files/9000000121.pdf"}, "version_id": "62892a5a-04bb-4a17-bffd-740103285c4c"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "jpn"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "thesis", "resourceuri": "http://purl.org/coar/resource_type/c_46ec"}]}, "item_title": "言語処理系におけるごみ集めとコード最適化に関する研究", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "言語処理系におけるごみ集めとコード最適化に関する研究", "subitem_title_language": "ja"}, {"subitem_title": "Studies on Garbage Collection and Code Optimization in Language Processors", "subitem_title_language": "en"}]}, "item_type_id": "10006", "owner": "3", "path": ["12"], "permalink_uri": "https://uec.repo.nii.ac.jp/records/1244", "pubdate": {"attribute_name": "PubDate", "attribute_value": "2010-02-15"}, "publish_date": "2010-02-15", "publish_status": "0", "recid": "1244", "relation": {}, "relation_version_is_last": true, "title": ["言語処理系におけるごみ集めとコード最適化に関する研究"], "weko_shared_id": -1}
言語処理系におけるごみ集めとコード最適化に関する研究
https://uec.repo.nii.ac.jp/records/1244
https://uec.repo.nii.ac.jp/records/124402532948-552e-4958-846d-bd865cb7af09
名前 / ファイル | ライセンス | アクション |
---|---|---|
9000000121.pdf (756.6 kB)
|
|
Item type | 学位論文 / Thesis or Dissertation(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2010-02-15 | |||||
タイトル | ||||||
言語 | ja | |||||
タイトル | 言語処理系におけるごみ集めとコード最適化に関する研究 | |||||
タイトル | ||||||
言語 | en | |||||
タイトル | Studies on Garbage Collection and Code Optimization in Language Processors | |||||
言語 | ||||||
言語 | jpn | |||||
資源タイプ | ||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_46ec | |||||
資源タイプ | thesis | |||||
著者 |
鈴木, 貢
× 鈴木, 貢 |
|||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | 本研究では,言語処理系の実装に関連する二つの事項を取り扱う.本論文の第1 部(第2 章~第4章)では,実行時系における記憶場所の動的な管理である「ごみ集め」に関して議論する.ごみ集めは,記号処理言語やオブジェクト指向型言語の実装には不可欠なしくみで,その性能が全体の性能を左右する.そして,第2 部(第5 章~第8 章)では,SIMD(Single Instruction Multiple Data-stream)命令の一種のレジスタ分割型ショートベクタ命令セット(以下SIMD 命令と略す)に注目し,翻訳系によるSIMD 命令向け最適化に関して議論する.この命令セットは,メディアデータ処理の高速化の安価な手法として考案され定着してきた.これには,従来のコード最適化技法を応用可能な事項もあるが,新しく開発する必要がある事項も多い.現状では,コンパイラによるSIMD 命令の自動生成は研究段階であるので,アセンブリ言語等を用いないとSIMD 命令の満足がいく活用ができない.第1 章では,二つの事項を研究するに至る背景について議論する.第2 章では,先ず,第1 部で取り扱うごみ集め問題を定式化した.次に,参照計数法,複写法,印掃法というごみ集めの三つの戦略を示した.そして,従来の印掃法のごみ集めでは解決されていなかった二つの問題を指摘し,関連する既存の成果を紹介し分析した.第3 章で議論している第一の問題は,印掃法ごみ集めの実行時間を小さくすることである.従来の印掃法ごみ集めは,記憶領域のサイズをS として,S に比例する時間が必要であった.これに対し,使用中の記憶の量をA として,理論上の計算量はAlogA,実用上はA に比例する実行時間で済む印掃法のごみ集めで,使用領域を圧縮するもの(以下印掃式圧縮型と略す)を提案した.これにより,A がS の1割以下という一般的な状況の下では,ごみ集めが高速化された.第4 章で議論している第二の問題は,「世代別ごみ集め」と呼ばれるごみ集めの手間を省く戦略を,印掃法の圧縮型ごみ集めに適用することである.世代別ごみ集めは,通常は,複写法のごみ集めとの組み合わせで実現される.ここでは,印掃法の圧縮型ごみ集めの生成順序保存という特徴を生かした方法を提案し,小さなオーバヘッドで世代別ごみ集めを実装する方法を示した.これにより,さらにごみ集めが高速化された.第5 章では,先ず,第2 部で取り扱うSIMD 命令の動作や種類を説明する.次に,コンパイラによるSIMD 命令の自動生成に関する問題点を指摘し,関連する既存の成果を紹介し分析する.そして,本研究での実装に関連する成果を紹介する.第6 章で議論している第一の問題は,SIMD 命令向けの言語仕様の拡張を使用していない(つまり通常の言語規格の範囲内で記述された)プログラムから,SIMD 命令の振る舞いに相当するオペレーションを抽出する方法である.このために,覗き穴最適化を応用した方法による最適化技法を提案した.第7 章で議論している第二の問題は,高級言語の汎整数拡張が,効果的なSIMD 命令の適用を阻害していることである.汎整数拡張とは,汎整数型(通常は計算機が効率よく処理できる整数型)より小さいサイズのデータは,演算に使用される前に汎整数型への符号拡張やゼロ拡張が施されるという仕様である.これに対して,なるべく小さいデータサイズによる演算で,汎整数拡張を行う場合と同じ結果を得るためのプログラム解析法を提案した.第8 章で議論している第三の問題は,実在する多くのベクタ処理向きのプログラムやベンチマークプログラムが,コンパイラによるSIMD 命令活用のベンチマークに適していないことである.そこで,これらの中の例題を分析し,SIMD 命令を効果的に適用できるように変形し,SIMD 命令向きのコーディングを示した.さらに,コンパイラのSIMD 命令の活用度を調べるためのベンチマークとして,各々の例題に対して,SIMD 命令の適用を容易にする種々の変形を組織的に施したプログラム集で,複数の変形版から成るものを用意した.最後に第9 章では,本研究で得られた成果を総括する.成果の一つは,記憶領域の使用効率が高く,実行時間も小さいごみ集めを提案したことである.それにより,記憶領域が乏しい計算機でも,近代的な言語が必須とするごみ集めを効率よく実現できる.もう一つは,SIMD 命令向けの最適化技術を提案し,実装し,評価し,実行性能の向上を示したことである.これにより,命令セットが異なる計算機間でも,同じメディアデータ処理プログラムを共有できるようになる. | |||||
学位名 | ||||||
学位名 | 博士(工学) | |||||
学位授与機関 | ||||||
学位授与機関名 | 電気通信大学 | |||||
学位授与年度 | ||||||
内容記述タイプ | Other | |||||
内容記述 | 2006 | |||||
学位授与年月日 | ||||||
学位授与年月日 | 2006-03-23 |