서브메뉴
검색
Heuristic-Hardware Co-Design for Large-Scale Optimization Problems
Heuristic-Hardware Co-Design for Large-Scale Optimization Problems
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20260202105224
- ISBN
- 9798291566473
- DDC
- 621.3
- 저자명
- Shukla, Aditya.
- 서명/저자
- Heuristic-Hardware Co-Design for Large-Scale Optimization Problems
- 발행사항
- [Sl] : University of Michigan, 2025
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2025
- 형태사항
- 173 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 87-03, Section: B.
- 주기사항
- Advisor: Erementchouk, Mikhail;Mazumder, Pinaki.
- 학위논문주기
- Thesis (Ph.D.)--University of Michigan, 2025.
- 초록/해제
- 요약Many real-world engineering problems involve hard combinatorial optimizations. Heuristic algorithms, trading off accuracy for time-to-solution, are crucial for their solvability. However, as the problem size increases, time becomes the critical factor and solving these problems motivates the development of more elaborate techniques.In my thesis, I adopt the approach of synergistic co-design of heuristics and computing platforms. I postulate that for scalability, besides providing competitive quality of solution in polynomial time, such deeply custom optimizing machines should be characterized by simplicity, homogeneity and parallelizability of operations and the independence from external computing resources. Bearing these features, I propose a novel class of custom computing machines aimed at solving large quadratic unconstrained binary optimization (QUBO) problems via continuous relaxation. The machines are simultaneously designed at the heuristic and hardware levels, and implementable using the accessible VLSI CMOS technology.At the heuristic level, I approximately solve the QUBO form of max-cut through its relaxed reformulation as two relatively tractable sub-problems. First, the binary constraint on the QUBO variables is relaxed, leading to a system of coupled 2D vectors that evolve to maximize a quantity closely related to the cut. The terminal states are generally non-binary and therefore must be rounded. Optimal rounding, the second sub-problem, is non-trivial as existing parametric rounding algorithms, due to their sequential nature, become the bottleneck.Along the directions of these problems, this work presents two QUBO machines. First, I present an analog QUBO machine that solves a relaxed problem using analog computing methods. The entire machine is designed at the circuit level to implement a network of almost-linearly coupled continuous spins. The analog variables are realized using capacitors and their coupling using a digital-to-analog converter. However, our reliance on external computing resources for optimal rounding and non-idealities inherent to analog computing limits the size of the problem that could be solved by the machine. In the second part of the work, I overcome these challenges and present a digital QUBO machine prototyped on a multi-FPGA system. The machine provides high quality solutions to arbitrary 1024-node weighted or 2048-node unweighted QUBO problem by simultaneously solving the relaxed QUBO problem and implementing an optimal rounding procedure in massively parallel fashion. To the best of our knowledge, this is the first self-contained scalable relaxation-based machine that directly solves the problem of optimal rounding.
- 일반주제명
- Computer engineering
- 일반주제명
- Computer science
- 일반주제명
- Information technology
- 일반주제명
- Electrical engineering
- 키워드
- Ising machines
- 키워드
- Graph coloring
- 키워드
- Maximum cut
- 기타저자
- University of Michigan Electrical and Computer Engineering
- 기본자료저록
- Dissertations Abstracts International. 87-03B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008260126s2025 us c eng d■001000017359849
■00520260202105224
■006m o d
■007cr#unu||||||||
■020 ▼a9798291566473
■035 ▼a(MiAaPQ)AAI32271837
■035 ▼a(MiAaPQ)umichrackham006205
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a621.3
■1001 ▼aShukla, Aditya.
■24510▼aHeuristic-Hardware Co-Design for Large-Scale Optimization Problems
■260 ▼a[Sl]▼bUniversity of Michigan▼c2025
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2025
■300 ▼a173 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 87-03, Section: B.
■500 ▼aAdvisor: Erementchouk, Mikhail;Mazumder, Pinaki.
■5021 ▼aThesis (Ph.D.)--University of Michigan, 2025.
■520 ▼aMany real-world engineering problems involve hard combinatorial optimizations. Heuristic algorithms, trading off accuracy for time-to-solution, are crucial for their solvability. However, as the problem size increases, time becomes the critical factor and solving these problems motivates the development of more elaborate techniques.In my thesis, I adopt the approach of synergistic co-design of heuristics and computing platforms. I postulate that for scalability, besides providing competitive quality of solution in polynomial time, such deeply custom optimizing machines should be characterized by simplicity, homogeneity and parallelizability of operations and the independence from external computing resources. Bearing these features, I propose a novel class of custom computing machines aimed at solving large quadratic unconstrained binary optimization (QUBO) problems via continuous relaxation. The machines are simultaneously designed at the heuristic and hardware levels, and implementable using the accessible VLSI CMOS technology.At the heuristic level, I approximately solve the QUBO form of max-cut through its relaxed reformulation as two relatively tractable sub-problems. First, the binary constraint on the QUBO variables is relaxed, leading to a system of coupled 2D vectors that evolve to maximize a quantity closely related to the cut. The terminal states are generally non-binary and therefore must be rounded. Optimal rounding, the second sub-problem, is non-trivial as existing parametric rounding algorithms, due to their sequential nature, become the bottleneck.Along the directions of these problems, this work presents two QUBO machines. First, I present an analog QUBO machine that solves a relaxed problem using analog computing methods. The entire machine is designed at the circuit level to implement a network of almost-linearly coupled continuous spins. The analog variables are realized using capacitors and their coupling using a digital-to-analog converter. However, our reliance on external computing resources for optimal rounding and non-idealities inherent to analog computing limits the size of the problem that could be solved by the machine. In the second part of the work, I overcome these challenges and present a digital QUBO machine prototyped on a multi-FPGA system. The machine provides high quality solutions to arbitrary 1024-node weighted or 2048-node unweighted QUBO problem by simultaneously solving the relaxed QUBO problem and implementing an optimal rounding procedure in massively parallel fashion. To the best of our knowledge, this is the first self-contained scalable relaxation-based machine that directly solves the problem of optimal rounding.
■590 ▼aSchool code: 0127.
■650 4▼aComputer engineering
■650 4▼aComputer science
■650 4▼aInformation technology
■650 4▼aElectrical engineering
■653 ▼aIsing machines
■653 ▼aCombinatorial optimization
■653 ▼aGraph coloring
■653 ▼aMaximum cut
■653 ▼aQuadratic unconstrained binary optimization
■690 ▼a0464
■690 ▼a0984
■690 ▼a0796
■690 ▼a0489
■690 ▼a0544
■71020▼aUniversity of Michigan▼bElectrical and Computer Engineering.
■7730 ▼tDissertations Abstracts International▼g87-03B.
■790 ▼a0127
■791 ▼aPh.D.
■792 ▼a2025
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17359849▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
