論文の概要: Enhanced Fast Boolean Matching based on Sensitivity Signatures Pruning
- arxiv url: http://arxiv.org/abs/2111.06213v1
- Date: Thu, 11 Nov 2021 14:06:56 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-12 15:05:51.425063
- Title: Enhanced Fast Boolean Matching based on Sensitivity Signatures Pruning
- Title（参考訳）: 感度シグネチャプラニングに基づく高速ブールマッチングの高速化
- Authors: Jiaxi Zhang, Liwei Ni, Shenggen Zheng, Hao Liu, Xiangfu Zou, Feng
Wang, Guojie Luo
- Abstract要約: ブールマッチングに感度を導入し、高速マッチングを強化するためにいくつかの感度関連シグネチャを設計する。
従来のコファクタ法や対称検出法と比較すると、感度は別の次元の一連のシグネチャである。
その結果,感度関連シグネチャは検索空間を極端に小さくし,最大3倍のスピードアップを達成できることがわかった。
- 参考スコア（独自算出の注目度）: 8.161723312848817
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Boolean matching is significant to digital integrated circuits design. An
exhaustive method for Boolean matching is computationally expensive even for
functions with only a few variables, because the time complexity of such an
algorithm for an n-variable Boolean function is $O(2^{n+1}n!)$. Sensitivity is
an important characteristic and a measure of the complexity of Boolean
functions. It has been used in analysis of the complexity of algorithms in
different fields. This measure could be regarded as a signature of Boolean
functions and has great potential to help reduce the search space of Boolean
matching.
In this paper, we introduce Boolean sensitivity into Boolean matching and
design several sensitivity-related signatures to enhance fast Boolean matching.
First, we propose some new signatures that relate sensitivity to Boolean
equivalence. Then, we prove that these signatures are prerequisites for Boolean
matching, which we can use to reduce the search space of the matching problem.
Besides, we develop a fast sensitivity calculation method to compute and
compare these signatures of two Boolean functions. Compared with the
traditional cofactor and symmetric detection methods, sensitivity is a series
of signatures of another dimension. We also show that sensitivity can be easily
integrated into traditional methods and distinguish the mismatched Boolean
functions faster. To the best of our knowledge, this is the first work that
introduces sensitivity to Boolean matching. The experimental results show that
sensitivity-related signatures we proposed in this paper can reduce the search
space to a very large extent, and perform up to 3x speedup over the
state-of-the-art Boolean matching methods.
- Abstract（参考訳）: ブールマッチングはデジタル集積回路設計において重要である。
n変数のブール関数に対するそのようなアルゴリズムの時間複雑性は$o(2^{n+1}n!)$であるので、ブールマッチングの徹底的な手法は数変数の関数でも計算的に高価である。
感度はブール関数の複雑さの重要な特徴であり測度である。
様々な分野におけるアルゴリズムの複雑さの分析に用いられている。
この測度はブール関数の符号と見なすことができ、ブールマッチングの探索空間を減少させる大きな可能性を持つ。
本稿では,booleanマッチングにboolean感度を導入するとともに,booleanマッチングの高速化のためにいくつかの感度関連シグネチャを設計する。
まず,ブール等価性に対する感度に関する新たなシグネチャを提案する。
そして,これらのシグネチャがブールマッチングの前提条件であることを証明する。
また、2つのブール関数のシグネチャを計算・比較するための高速感度計算法を開発した。
従来の共因子および対称検出法と比較して、感度は別の次元の一連のシグネチャである。
また,感度を従来の手法と容易に統合でき,ミスマッチしたブール関数を高速に区別できることを示した。
私たちの知る限りでは、Booleanマッチングに感度を導入するのはこれが初めてです。
実験の結果,本論文で提案した感度関連シグネチャは,探索空間を極端に小さくし,最先端のブールマッチング法に対して最大3倍の高速化を実現することができた。
関連論文リスト
- BoolQuestions: Does Dense Retrieval Understand Boolean Logic in Language? [88.29075896295357]
まず,現在の検索システムが,言語に暗示されるブール論理を理解できるかを検討する。
広範な実験結果から,現在の高密度検索システムはブール論理を十分に理解していないという結論を導いた。
本研究では,研究コミュニティの強力な基盤となるコントラスト的連続学習手法を提案する。
論文 参考訳（メタデータ） (2024-11-19T05:19:53Z) - A New Angle: On Evolving Rotation Symmetric Boolean Functions [32.90791284928444]
本稿では、いくつかの進化的アルゴリズムを用いて、異なる性質を持つ回転対称ブール関数を進化させる。
驚いたことに、ビットストリングと浮動小数点エンコーディングはツリーエンコーディングよりもうまく機能している。
論文 参考訳（メタデータ） (2023-11-20T16:16:45Z) - Learning to Select SAT Encodings for Pseudo-Boolean and Linear Integer
Constraints [1.1371889042789218]
本稿では,制約問題に対する標準的な特徴セットを用いて,効率よく符号化を選択することができることを示す。
擬似ブール制約と線形制約に特化して設計された,新しい機能セットにより,性能が向上する。
結果は、同じ機能セットを使用する場合、AutoFolioと良好に比較されます。
論文 参考訳（メタデータ） (2023-07-18T15:26:46Z) - Better Than Whitespace: Information Retrieval for Languages without
Custom Tokenizers [48.036317742487796]
語彙マッチング検索アルゴリズムのための新しいトークン化手法を提案する。
教師なしのデータから自動的に構築できるWordPieceトークンライザを使用します。
以上の結果から,mBERTトークン化器は,ほとんどの言語において,"アウト・オブ・ザ・ボックス(out of the box)"を検索するための強い関連信号を提供することがわかった。
論文 参考訳（メタデータ） (2022-10-11T14:32:46Z) - Breaking BERT: Evaluating and Optimizing Sparsified Attention [13.529939025511242]
一連のアブレーション実験により,スペーシフィケーションパターンの影響を評価した。
また,少なくとも78%のスパースを有する注意を用いても,後続の変圧器層に適用した場合,性能にはほとんど影響を与えないことがわかった。
論文 参考訳（メタデータ） (2022-10-07T22:32:27Z) - Estimating the hardness of SAT encodings for Logical Equivalence
Checking of Boolean circuits [58.83758257568434]
LEC インスタンスの SAT 符号化の硬さは SAT パーティショニングでは textitw.r. と推定できることを示す。
そこで本研究では, SAT符号化の難易度を精度良く推定できるパーティショニング法を提案する。
論文 参考訳（メタデータ） (2022-10-04T09:19:13Z) - Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。
実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。
本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-13T02:44:05Z) - Sensitivity as a Complexity Measure for Sequence Classification Tasks [24.246784593571626]
標準のシーケンス分類法は低感度関数の学習に偏っているため、高感度を必要とするタスクがより困難である。
15のNLPタスクで感度を推定し、単純なテキスト分類タスクよりもGLUEで収集された挑戦的なタスクで感度が高いことを発見した。
論文 参考訳（メタデータ） (2021-04-21T03:56:59Z) - A Heuristic Approach to Two Level Boolean Minimization Derived from
Karnaugh Mapping [4.0556962308523685]
Karnaugh や Quine-McCluskey のような既存の手法は、リテラルの量が増加するにつれて、複雑さが指数関数的に増加するのでスケールできない。
この新しい手法は、基本写像法、カルノー写像、および真理表から派生した。
論文 参考訳（メタデータ） (2020-08-21T05:10:10Z) - Faster Person Re-Identification [68.22203008760269]
本稿では,新しいハッシュコード検索戦略を定式化することによって,高速ReIDのための新しいソリューションを提案する。
より短いコードを使用して、より正確なReIDのいくつかのトップ候補を洗練するために、より広い一致の類似性を粗くランク付けし、より長いコードを使用する。
2つのデータセットに対する実験結果から,提案手法(CtF)は現在のハッシュReID法よりも8%精度が高いだけでなく,5倍高速であることがわかった。
論文 参考訳（メタデータ） (2020-08-16T03:02:49Z) - Glushkov's construction for functional subsequential transducers [91.3755431537592]
グルシコフの構成は多くの興味深い性質を持ち、トランスデューサに適用するとさらに明らかになる。
正規表現の特別な風味を導入し、効率よく$epsilon$-free 機能的次数重み付き有限状態トランスデューサに変換することができる。
論文 参考訳（メタデータ） (2020-08-05T17:09:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。