Show simple item record

dc.contributor.advisorSrikant, Y N
dc.contributor.authorCheramangalath, Unnikrishnan
dc.date.accessioned2018-08-20T07:25:01Z
dc.date.accessioned2018-08-28T09:15:02Z
dc.date.available2018-08-20T07:25:01Z
dc.date.available2018-08-28T09:15:02Z
dc.date.issued2018-08-20
dc.date.submitted2017
dc.identifier.urihttp://etd.iisc.ac.in/handle/2005/3978
dc.identifier.abstracthttp://etd.iisc.ac.in/static/etd/abstracts/4866/G28548-Abs.pdfen_US
dc.description.abstractGraphs model relationships across real-world entities in web graphs, social network graphs, and road network graphs. Graph algorithms analyze and transform a graph to discover graph properties or to apply a computation. For instance, a pagerank algorithm computes a rank for each page in a webgraph, and a community detection algorithm discovers likely communities in a social network, while a shortest path algorithm computes the quickest way to reach a place from another, in a road network. In Domains such as social information systems, the number of edges can be in billions or trillions. Such large graphs are processed on distributed computer systems or clusters. Graph algorithms can be executed on multi-core CPUs, GPUs with thousands of cores, multi-GPU devices, and CPU+GPU clusters, depending on the size of the graph object. While programming such algorithms on heterogeneous targets, a programmer is required to deal with parallelism and and also manage explicit data communication between distributed devices. This implies that a programmer is required to learn CUDA, OpenMP, MPI, etc., and also the details of the hardware architecture. Such codes are error prone and di cult to debug. A Domain Speci c Language (DSL) which hides all the hardware details and lets the programmer concentrate only the algorithmic logic will be very useful. With this as the research goal, Falcon, graph DSL and its compiler have been developed. Falcon programs are explicitly parallel and Falcon hides all the hardware details from the programmer. Large graphs that do not t into the memory of a single device are automatically partitioned by the Falcon compiler. Another feature of Falcon is that it supports mutation of graph objects and thus enables programming dynamic graph algorithms. The Falcon compiler converts a single DSL code to heterogeneous targets such as multi-core CPUs, GPUs, multi-GPU devices, and CPU+GPU clusters. Compiled codes of Falcon match or outperform state-of-the-art graph frameworks for di erent target platforms and benchmarks.en_US
dc.language.isoen_USen_US
dc.relation.ispartofseriesG28548en_US
dc.subjectSparse Codingen_US
dc.subjectGraph Algorithmsen_US
dc.subjectFalconen_US
dc.subjectGraph Manipulation Languageen_US
dc.subjectMesh Algorithmsen_US
dc.subjectFalcon Graphen_US
dc.subjectDomain Specific Language (DSL)en_US
dc.subjectR-MAT Graphen_US
dc.subjectLarge-Scale Graphsen_US
dc.subjectHypergraphsen_US
dc.subjectWebgraphsen_US
dc.subject.classificationComputer Scienceen_US
dc.titleFalcon : A Graph Manipulation Language for Distributed Heterogeneous Systemsen_US
dc.typeThesisen_US
dc.degree.namePhDen_US
dc.degree.levelDoctoralen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record