{"created":"2025-01-18T22:59:35.288968+00:00","updated":"2025-01-22T17:20:44.098350+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00029844","sets":["1164:2240:2313:2316"]},"path":["2316"],"owner":"1","recid":"29844","title":["閾値関数のBDDの並列実装"],"pubdate":{"attribute_name":"公開日","attribute_value":"1995-08-24"},"_buckets":{"deposit":"d648b748-4804-4cbc-9738-e7b3d634cd85"},"_deposit":{"id":"29844","pid":{"type":"depid","value":"29844","revision_id":0},"owners":[1],"status":"published","created_by":1},"item_title":"閾値関数のBDDの並列実装","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"閾値関数のBDDの並列実装"},{"subitem_title":"PARALLEL CONSTRUCTION OF A BDD REPRESENTING A THRESHOLD FUNCTION","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"1995-08-24","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"東京大学大学院理学系研究科情報科学専攻"},{"subitem_text_value":"東京大学大学院理学系研究科情報科学専攻"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Department of Information Science, Faculty of Science, the University of Tokyo","subitem_text_language":"en"},{"subitem_text_value":"Department of Information Science, Faculty of Science, the University of Tokyo","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/29844/files/IPSJ-HPC95057013.pdf"},"date":[{"dateType":"Available","dateValue":"1997-08-24"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-HPC95057013.pdf","filesize":[{"value":"403.2 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"14"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"65138f53-431b-4a35-9272-911437c5b3e0","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 1995 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"丹羽, 純平"},{"creatorName":"今井, 浩"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Junpei, Niwa","creatorNameLang":"en"},{"creatorName":"Hiroshi, Imai","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN10463942","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"Akersによって提案された二分決定グラフ(D)は、論理関数を表現するDACである。BryantによるBDD間の論理演算を効率良く行なうアルゴリズムにより、BDDはVLSI　CAD等の様々な分野で使われるようになった。近年では組合せ問題にも応用されるようになった。本稿では、閾値関数を表すBDDを構築する新しいアルゴリズムを提案する。動的計画法を用いた前処理を行なった後でBDDを出力サイズに比例した計算量でトップダウンに構築するものである。我々は更に上述のアルゴリズムを並列化してそれをAP1000＋上で実装し、実験により既存のアルゴリズムで構築できなかったサイズのBDDを迅速に構築できることを示した。","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"A Binary Decision Diagram (BDD), proposed by Akers, is a DAG representing a boolean function. Through the development of the efficient algorithms of boolean operations on BDDs Bryant, it has been used in various fields, such as VLSI CAD. Recently it has been applied to combinatorics. We propose a new algorithm of constructing a BDD representing a threshold function. After a preprocessing stage using a dynamic programing, we construct the BDD in a top-down manner with time proportional to the output size. Furthermore we parallelize the algorithm and implement it on AP1000+, and the experiment shows that the BDD which could not be constructed by the existing algorithm is constructed quickly.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"78","bibliographic_titles":[{"bibliographic_title":"情報処理学会研究報告ハイパフォーマンスコンピューティング（HPC）"}],"bibliographicPageStart":"73","bibliographicIssueDates":{"bibliographicIssueDate":"1995-08-24","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"81(1995-HPC-057)","bibliographicVolumeNumber":"1995"}]},"relation_version_is_last":true,"weko_creator_id":"1"},"id":29844,"links":{}}