Search

Your search keyword '"Chen, Yean-Ru"' showing total 34 results
Start Over Author "Chen, Yean-Ru"
34 results on '"Chen, Yean-Ru"'

1. A Parallel and Distributed Quantum SAT Solver Based on Entanglement and Quantum Teleportation

Author

Lin, Shang-Wei, Wang, Tzu-Fan, Chen, Yean-Ru, Hou, Zhe, Sanán, David, and Teo, Yon Shin

Subjects
Quantum Physics, Computer Science - Distributed, Parallel, and Cluster Computing
Abstract

Boolean satisfiability (SAT) solving is a fundamental problem in computer science. Finding efficient algorithms for SAT solving has broad implications in many areas of computer science and beyond. Quantum SAT solvers have been proposed in the literature based on Grover's algorithm. Although existing quantum SAT solvers can consider all possible inputs at once, they evaluate each clause in the formula one by one sequentially, making the time complexity O(m) -- linear to the number of clauses m -- per Grover iteration. In this work, we develop a parallel quantum SAT solver, which reduces the time complexity in each iteration from linear time O(m) to constant time O(1) by utilising extra entangled qubits. To further improve the scalability of our solution in case of extremely large problems, we develop a distributed version of the proposed parallel SAT solver based on quantum teleportation such that the total qubits required are shared and distributed among a set of quantum computers (nodes), and the quantum SAT solving is accomplished collaboratively by all the nodes. We have proved the correctness of our approaches and demonstrated them in simulations.

Published
2023

2. A Quantum SMT Solver for Bit-Vector Theory

Author

Lin, Shang-Wei, Chen, Si-Han, Wang, Tzu-Fan, and Chen, Yean-Ru

Subjects
Computer Science - Logic in Computer Science, Quantum Physics
Abstract

Given a formula $F$ of satisfiability modulo theory (SMT), the classical SMT solver tries to (1) abstract $F$ as a Boolean formula $F_B$, (2) find a Boolean solution to $F_B$, and (3) check whether the Boolean solution is consistent with the theory. Steps~{(2)} and (3) may need to be performed back and forth until a consistent solution is found. In this work, we develop a quantum SMT solver for the bit-vector theory. With the characteristic of superposition in quantum system, our solver is able to consider all the inputs simultaneously and check their consistency between Boolean and the theory domains in one shot.

Published
2023

7. VERTAF/Multi-Core: A SysML-Based Application Framework for Multi-Core Embedded Software Development

Author

Hsiung, Pao-Ann, Lin, Chao-Sheng, Lin, Shang-Wei, Chen, Yean-Ru, Lu, Chun-Hsien, Tong, Sheng-Ya, Su, Wan-Ting, Shih, Chihhsiong, Koong, Chorng-Shiuh, Hsueh, Nien-Lin, Chang, Chih-Hung, Chu, William C., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Hua, Arrems, editor, and Chang, Shih-Liang, editor

Published
2009
Full Text
View/download PDF

8. Modeling and Automatic Failure Analysis of Safety-Critical Systems Using Extended Safecharts

Author

Chen, Yean-Ru, Hsiung, Pao-Ann, Chen, Sao-Jie, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Saglietti, Francesca, editor, and Oster, Norbert, editor

Published
2007
Full Text
View/download PDF

9. Model Checking Timed Systems with Urgencies

Author

Hsiung, Pao-Ann, Lin, Shang-Wei, Chen, Yean-Ru, Huang, Chun-Hsian, Yeh, Jia-Jen, Sun, Hong-Yu, Lin, Chao-Sheng, Liao, Hsiao-Win, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Graf, Susanne, editor, and Zhang, Wenhui, editor

Published
2006
Full Text
View/download PDF

10. Model Checking Prioritized Timed Automata

Author

Lin, Shang-Wei, Hsiung, Pao-Ann, Huang, Chun-Hsian, Chen, Yean-Ru, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Peled, Doron A., editor, and Tsay, Yih-Kuen, editor

Published
2005
Full Text
View/download PDF

16. SMT Solver With Hardware Acceleration

Author

Chen, Yean-Ru, Chen, Si-Han, and Lin, Shang-Wei

Abstract

Satisfiability modulo theories (SMTs), an extension of Boolean satisfiability (SAT) problem, is widely used in many application domains because of its rich expressiveness. Thus, there are many works trying to speedup the process of SAT/SMT solving. In this work, we develop a framework by proposing a new hardware architecture to solve the SMT problem for the theory of quantifier free linear real arithmetic (QF-LRA) to speedup the SMT solving process. The new proposed architecture framework consists of a hardware SAT solver and a hardware Simplex solver. Our hardware SAT solver has an optimized Boolean constraint propagation process with a pipeline structure and a nonchronological backtracking mechanism, while our hardware Simplex solver supports parallel operation flow inside the Simplex iteration to execute the selection operations parallelly with the pivot operation and the row selection mechanism to avoid unnecessary row computation and increase the resource utilization. According to our experimental results, the proposed framework can achieve from 2.539 up to 1561.181 times speedup compared with software SMT solvers in our selected 40 benchmarks.

Published
2023
Full Text
View/download PDF

17. VERTAF/Multi-Core: A SysML-Based Application Framework for Multi-Core Embedded Software Development

Author

Hsiung, Pao-Ann, primary, Lin, Chao-Sheng, additional, Lin, Shang-Wei, additional, Chen, Yean-Ru, additional, Lu, Chun-Hsien, additional, Tong, Sheng-Ya, additional, Su, Wan-Ting, additional, Shih, Chihhsiong, additional, Koong, Chorng-Shiuh, additional, Hsueh, Nien-Lin, additional, Chang, Chih-Hung, additional, and Chu, William C., additional

Published
2009
Full Text
View/download PDF

19. Model Checking Timed Systems with Urgencies

Author

Hsiung, Pao-Ann, primary, Lin, Shang-Wei, additional, Chen, Yean-Ru, additional, Huang, Chun-Hsian, additional, Yeh, Jia-Jen, additional, Sun, Hong-Yu, additional, Lin, Chao-Sheng, additional, and Liao, Hsiao-Win, additional

Published
2006
Full Text
View/download PDF

23. Multicore Hardware-software Design and Verification Techniques

Author

Hsiung, Pao-Ann, Chen, Yean-Ru, Lin, Chao-Sheng, Hsiung, Pao-Ann, Chen, Yean-Ru, and Lin, Chao-Sheng

Subjects
Computer input-output equipment, Computer software--Development, Software engineering
Abstract

The surge of multicore processors coming into the market and on users'desktops has made parallel computing the focus of attention once again. This time, however, it is led by the industry, which ensures that multicore computing is here to stay. Nevertheless, there is still so much research work to be done in multicore hardware-software designs before consumer applications can leverage the benefits of this new paradigm. This e-book is being put forward as a platform for immediate collection of state-of-the-art technologies in both hardware and software designs for multicore computing. With the burgeoning prevalence of multicore processors in embedded systems, real-time systems, multimedia systems, bioinformatics systems, network systems, to list a few, this e-book attempts to cover the design and verification issues related to different application domains as a singular source of reference to the state-of-the-art techniques in multicore processor design and software programming that covers multiple application domains. This e-book will be of immense help to system and software engineers, including both experts and non-experts in parallel computing.

Published
2011

Catalog

Books, media, physical & digital resources
See catalog results