MARC

 008260126s2021        us                              c    eng  d
■001000017360535
■00520260202105543
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798263398873
■035    ▼a(MiAaPQ)AAI32315444
■035    ▼a(MiAaPQ)GeorgiaTech66166
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a519.5
■1001  ▼aYasar,  Abdurrahman.
■24510▼aTowards  Performance  Portable  Graph  Algorithms
■260    ▼a[Sl]▼bGeorgia  Institute  of  Technology▼c2021
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2021
■300    ▼a275  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  87-06,  Section:  B.
■500    ▼aAdvisor:  Catalyurek,  Umit  V.
■5021  ▼aThesis  (Ph.D.)--Georgia  Institute  of  Technology,  2021.
■520    ▼aIn  today's  data-driven  world  and  heterogeneous  computing  environments  processing  large-scale  graphs  in  an  architecture  agnostic  manner  has  become  more  important  than  ever  before.  Therefore,  there  has  been  a  significant  interest  in  high-performance  graph  processing.  Traditionally,  hand-optimized  high-performance  computing  (HPC)  solutions  have  been  studied  and  used  to  implement  highly  efficient  and  scalable  graph  algorithms.  In  recent  years,  after  the  big  data  movement,  to  bring  parallel  computing  to  the  masses,  researchers  also  proposed  several  graph  processing  and  management  systems  to  handle  large-scale  graphs.  Hand  optimized  HPC  approaches  require  high  expertise  and  graph  processing  frameworks  suffer  from  expressibility  and  performance.  Both  approaches  have  portability  issues.This  work  proposes  that  block-based  graph  algorithms  offer  a  sweet  spot  between  efficient  parallelism  and  architecture  agnostic  algorithm  design  for  a  wide  class  of  graph  problems  that  performs  close  to  hand-optimized  HPC  implementations.In  this  work,  we  first  show  how  we  can  solve  graph  merging  and  triangle  counting  problems  using  block-based  approaches.  First,  we  propose  a  partitioning  for  the  computation  space  to  solve  the  graph  merging  problem.  We  propose  a  novel,  fast  graph  merging  algorithm,  and  a  data-parallel,  architecture  (resource)-aware  scalable  graph  merging  framework.  Second,  we  propose  a  coarse-grained  triangle  counting  algorithm  for  shared-memory  multicore  machines.  That  algorithm  aims  to  increase  cache  locality  by  considering  the  natural  order  of  the  given  graphs  to  partition  the  computation  among  threads.  However,  coarse-grain  approaches  perform  poorly  on  distributed  and  (or)  heterogeneous  environments.  Therefore,  we  propose  a  specific  2D  partitioning  strategy,  named  as  symmetric  rectilinear  partitioning  and  a  medium-grained  triangle  counting  formulation  on  top  of  this  partitioning  which  makes  the  algorithm  naturally  suitable  for  task-based  execution  on  shared  and  distributed-memory  systems  as  well  as  on  heterogeneous  architectures.Furthermore,  using  proposed  partitioning  and  parallelization  strategies,  we  propose  a  block-based  algorithmic  framework  for  parallel  graph  processing  on  heterogeneous  platforms;  PGAbB.  In  a  heterogeneous  setting,  PGAbB  aims  to  maximally  leverage  from  different  architectures  by  implementing  a  task-based  execution  on  top  of  a  block-based  programming  model.  We  further  propose  algorithmic  optimizations  for  scheduling,  load-balancing,  and  reducing  the  data-movement  complexities  of  these  applications  for  real-world  inputs.
■590    ▼aSchool  code:  0078.
■650  4▼aSimilarity  measures
■650  4▼aGraphs
■650  4▼aOptimization  techniques
■650  4▼aComputer  science
■653    ▼aHigh-performance  computing
■653    ▼aGraph  processing
■690    ▼a0984
■71020▼aGeorgia  Institute  of  Technology.
■7730  ▼tDissertations  Abstracts  International▼g87-06B.
■790    ▼a0078
■791    ▼aPh.D.
■792    ▼a2021
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17360535▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서