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이  자료의  원문은  한국교육학술정보원에서  제공합니다.

Preview

Export

ChatGPT Discussion

AI Recommended Related Books