類別:

高品質分散式圖著色演算法

Wed, 01 Jan 2025 00:00:00 GMT

標題: 高品質分散式圖著色演算法; Distributed High-Quality Graph Coloring Algorithm on GPUs 作者: 吳建賢; Chien-Hsien Wu 摘要: 圖著色（Graph Coloring）是一種基礎的演算法，目的是將顏色分配給圖形的節點，且相鄰節點不能擁有相同的顏色。在平行圖著色演算法中，主要評估兩個參數：顏色的品質與執行速度。我們提出的優化包含兩個部分：首先，我們重新設計 JP-SL 的優先級分配流程，以減少全域頂點掃描的次數並在執行過程中更有效地利用平行化。其次，我們將大規模圖劃分為多個子圖，並將其分配至多個 GPU 上同時運行，以進一步提升整體執行效率。; Graph coloring is a fundamental problem involving the assignment of colors to the vertices of a graph, ensuring that no two adjacent vertices possess the same color. In parallel graph coloring, two primary parameters are evaluated: color quality and execution speed. Our optimization methodology has two parts. We first improve priority allocation by re-engineering JP-SL to minimize global vertex scans and optimize parallelism during execution. Secondly, we enhance the overall runtime by splitting the extensive graph into subgraphs and allocating them across many GPUs for concurrent execution.

量子電路驗證方法與架構：模擬、等價性檢查與動態斷言

Wed, 01 Jan 2025 00:00:00 GMT

標題: 量子電路驗證方法與架構：模擬、等價性檢查與動態斷言; Methods and Framework for Quantum Circuit Verification: Simulation, Equivalence Checking, and Runtime Assertion 作者: 陳天富; Tian-Fu Chen 摘要: 驗證對於確保量子計算系統的正確性至關重要。然而，不同於傳統計算系統的驗證技術之成熟，量子計算至今仍嚴重缺乏系統化和自動化的驗證方法。我們發展了量子電路驗證的方法與框架，同時涵蓋靜態與動態驗證技術，包括模擬、等價性檢查、布林匹配以及動態斷言。我們的量子電路模擬工具允許使用者計算滿足自定義性質的量子態的精確機率或期望值，為量子程式設計與測試提供有效的手段。實驗中的案例研究顯示，我們的模擬工具能夠超越現有工具的能力，提供精確的量子電路分析和驗證。針對形式化驗證方法，有鑑於現有的等價性檢查方法缺乏足夠的通用性，難以處理日趨複雜的高級電路特性，因此我們提出了一個組合量子電路的一般模型，並由此定義了量子電路的部分等價關係，以及開發了相應的等價性檢查演算法。我們相信這些技術能夠涵蓋絕大多數──若非全部──的組合量子電路應用場景。從等價性的另一個角度來說，我們提供了第一個針對可逆邏輯電路的布林匹配問題的完整研究，包含傳統或量子演算法及其計算複雜度。值得注意的是，針對尋找輸入端的取反與排列以使兩個電路等價的問題，我們開發了多項式時間的量子演算法，而其經典對應方法的複雜度則為指數級。此一結果可被認為是設計自動化領域中首個指數級加速的演算法。針對動態驗證，藉由利用量子電路的消失態，我們提出了第一個量子電路動態斷言的通用框架，並能夠在錯誤偵測能力與斷言電路複雜度之間提供靈活的權衡空間。實驗顯示了我們的方法在通用性與有效性方面的獨特優勢，能夠提升量子電路在各類基準測試中的執行效率與成功率。本研究為量子程式驗證的未來奠定了廣泛的基礎，並希望所提出的方法與框架能推動量子程式設計自動化的發展。; Verification is essential for ensuring the correctness of quantum computing systems, yet systematic and automated approaches remain far behind their classical counterparts. We present methods and frameworks for quantum circuit verification, covering both static and dynamic approaches, including simulation, equivalence checking, Boolean matching, and runtime assertion. Our simulation tool allows users to query exact probabilities or expectation values of user-defined quantum state properties, thereby enhancing program design and testing. Case studies demonstrate its unique ability to support exact quantum circuit analysis and verification beyond the capabilities of existing tools. For formal verification, motivated by the lack of generality of existing equivalence checking methods in handling advanced circuit features, we propose a general model of composable quantum circuits, formalize partial equivalence relations, and develop corresponding algorithms, which are capable of encompassing most, if not all, composable quantum circuits. From another perspective on equivalence, we provide the first comprehensive characterization of algorithms and the computational complexity of Boolean matching reversible logic circuits. Notably, we develop polynomial-time quantum algorithms that identify input negations and permutations to make two circuits equivalent, while the classical complexity is exponential. This result arguably achieves the first exponential speedup for a design automation task. For dynamic verification, we introduce the first general framework for quantum circuit runtime assertion by exploring vanishing states of quantum programs, offering flexible trade-offs between error-detection power and assertion circuit complexity. Experiments show the unique benefits of our method in generality and effectiveness, improving quantum circuit execution efficiency and success rates in various benchmarks. This work establishes a versatile foundation for the future of quantum program verification, and we hope that the proposed methods and frameworks help advance the automation of quantum program design.

適用於氮化鎵LLC諧振轉換器之具有閘極振鈴抑制及可調式空白時間控制之閘極驅動積體電路

Thu, 01 Jan 2026 00:00:00 GMT

標題: 適用於氮化鎵LLC諧振轉換器之具有閘極振鈴抑制及可調式空白時間控制之閘極驅動積體電路; A Gate Driver IC with Gate Ringing Suppression and Adaptive Dead-Time Control for GaN-Based LLC Resonant Converter 作者: 莊心慈; Hsin-Tzu Chuang 摘要: 氮化鎵高電子遷移率電晶體憑藉其優異的切換特性，已成為實現高頻與高功率密度轉換器的關鍵技術。然而，要充分發揮氮化鎵元件的潛力，面臨著嚴峻的驅動挑戰。氮化鎵極快的切換速度與電路寄生電感交互作用，容易引發嚴重的閘極電壓振鈴；考慮到氮化鎵嚴格的閘極崩潰電壓限制，這嚴重威脅了元件的可靠度。此外，在如 LLC 等諧振拓撲中，傳統的固定死區時間設定往往導致過長的反向導通損耗或災難性的直通電流。現有的數位自適應解決方案通常存在收斂速度慢的問題，且缺乏實現完整軟切換管理所需的高側偵測能力。為解決上述問題，本論文提出了一款全整合式閘極驅動晶片。本首先，本論文提出了一種閘極振鈴抑制機制。該機制透過具有自終止特性的高側電流模式架構實現，能夠主動抑制寄生振盪，從而在不增加靜態功耗的情況下實現可靠運作。其次，提出了雙邊自適應死區時間控制技術。透過即時檢測開關轉換，該控制器逐週期優化死區時間，有效消除直通風險並最大限度地降低體反向導通損耗。本論文之晶片採用 TSMC 0.18 µm HV BCD 製程。基於 500 kHz、120 W 48V 轉 12V 規格之氮化鎵 LLC 轉換器設計，量測結果驗證了閘極振鈴抑制的效能；在 48V 輸入條件下，本設計無需外部阻尼電阻即成功消除了振盪。此外，在降壓測試條件下，自適應死區控制器在不同負載中皆能成功調節死區時間，與傳統固定死區方案相比，顯著提升了系統效率與可靠度。; Gallium Nitride (GaN) HEMTs have become a key technology for high-frequency converters due to their superior switching characteristics. However, driving GaN devices presents significant challenges. The high switching speed, coupled with parasitic inductances, often induces severe gate ringing. Furthermore, in LLC resonant converters, fixed dead-time settings typically result in excessive reverse conduction losses or catastrophic shoot-through. Existing adaptive solutions often suffer from slow convergence and lack the necessary high-side sensing capability. To address these, this thesis presents a fully integrated gate driver. First, a gate ringing suppression mechanism is proposed. Implemented via a high-side current-mode architecture with self-termination, this design actively damps parasitic oscillations, achieving reliable operation without static power dissipation. Second, a dual-sided adaptive dead-time control (ADTC) technique is introduced. By detecting switching transitions in real-time, the controller optimizes the dead-time duration cycle-by-cycle, effectively eliminating shoot-through risks and minimizing reverse conduction losses. The proposed chip is fabricated using TSMC 0.18-μm HV BCD technology. Experimental results from a 500 kHz, 120 W 48V to 12V GaN-based LLC resonant converter design validate the efficacy of gate ringing suppression; at 48 V input, the proposed architecture successfully eliminates oscillations without the need for external damping resistors. Additionally, the adaptive controller is verified under scaled-down operating conditions to successfully regulate dead-time across different loads, significantly improving efficiency and reliability compared to fixed dead-time solutions.

適用於低溫的14位元500 MS/s可合成數位類比轉換器和10位元5 GS/s 具切換突波消除技術之數位類比轉換器

Wed, 01 Jan 2025 00:00:00 GMT

標題: 適用於低溫的14位元500 MS/s可合成數位類比轉換器和10位元5 GS/s 具切換突波消除技術之數位類比轉換器; A 14-bit 500-MS/s Synthesizable and a 10-bit 5-GS/s with Switching Glitch Cancellation Current-Steering DAC for Cryogenic Applications 作者: 翁子婷; Zih-Ting Weng 摘要: 本論文提出兩顆採用 40-nm CMOS 製程的電流式數位類比轉換器，分別針對室溫與低溫操作進行設計。第一顆為 14位元 500-MS/s 的可合成電流式數位類比轉換器，利用數位自動佈局繞線工具實現，並透過單元電流源群聚、專用偏壓軌及插入式繞線結構來減輕自動繞線造成的時間偏差與寄生耦合，得以大幅縮短佈局時間。此數位類比轉換器在供應電壓1.1 V，功耗12.42 mW下於 300 K 可達到超過 50 dBc 的 SFDR 與低於 −66 dBc 的 IM3，在 4 K 時則達到超過 43 dBc 的 SFDR 與低於 −66 dBc 的 IM3。第二顆為 10位元 5-GS/s 的電流式數位類比轉換器，採用切換突波消除技術，其輔助單元的電流僅使用主電流單元的十六分之一倍以降低額外功耗與面積。此數位類比轉換器功耗 72 mW、核心面積為0.054 mm²，在高頻下可大幅提升線性度：於 2.47 GHz 時 SFDR 分別在 300 K 與 4 K 改善最多 6 dBc 與 4 dBc，在頻率為 2.4685±0.0005 GHz的雙音測試下 IM3 亦分別在 300 K 與 4 K 改善超過 12 dBc 與 8 dBc。結果顯示本研究提出的數位類比轉換器架構具備低溫相容、高速運作、線性度提升與降低設計複雜度的優點。; This thesis presents two current-steering digital-to-analog converters (CS-DACs) fabricated in 40-nm CMOS technology for both room-temperature and cryogenic operation. The first design is a 14-bit 500-MS/s synthesizable CS-DAC implemented using digital place-and-route tools. Layout challenges such as auto-routed timing skews and parasitic coupling are mitigated through clustered unit-cell placement, dedicated bias rails, and plug-in routing structures, enabling a significant reduction in layout time while achieving >50 dBc SFDR and <−66 dBc IM3 at 300 K, and >43 dBc SFDR and <−66 dBc IM3 at 4 K while consuming 12.42 mW from a 1.1 V supply. The second design is a 10-bit 5-GS/s CS-DAC with switching glitch cancellation (SGC) is also presented, where the SGC circuit operates at 1/16 of the main current unit to minimize power and area overhead. Consuming 72 mW with a core area of 0.054 mm², this DAC demonstrates significant high-frequency linearity improvement, enhancing the SFDR by up to 6 dBc at 300 K and 4 dBc at 4 K at 2.47 GHz, and improving IM3 by more than 12 dBc at 300 K and 8 dBc at 4 K for two-tone tests with 2.4685±0.0005GHz. These results validate efficient, cryogenic-compatible, and high-speed DAC architectures that achieve reduced design effort and improved linearity.