Search

High performance graph processing poses significant challenges for both algorithm and platform designers due to the large performance variability it exhibits: performance depends on the algorithm, the dataset, and the (hardware/software) platform. Traditionally, performance variability is tackled by extensive benchmarking, modeling, and, eventually, better or smarter algorithms. Our own research into the impact of datasets on the performance of graph algorithms has convinced us that such extensive benchmarking is very difficult for graph processing simply because we lack input data: the public datasets and graph generation tools currently available are insufficient for a systematic investigation of the impact of different graph properties. In this work we propose to alleviate this problem by using evolutionary computing as a method to generate graphs. Our goal is allow users to request graphs with a given set of properties (e.g., number of vertices, number of edges, degree distribution), and enable the generator to evolve graphs until they satisfy the request. Such a fine-grain, flexible exploration of graphs and their properties will finally enable a statistical take on performance analysis and modeling for graph processing. To this end, our work-in-progress paper presents the design of our generator, discusses the challenges and trade-offs to be encountered, and reveals our preliminary results.

Software abstractions are crucial to effectively program heterogeneous Multi-Processor Systems on Chip (MPSoCs). Prime examples of such abstractions are Kahn Process Networks (KPNs) and execution traces. When modeling computation as a KPN, one of the key challenges is to obtain a good mapping, i.e., an assignment of logical computation and communication to physical resources. In this paper we compare two system-level frameworks for solving the mapping problem: Sesame and MAPS. These frameworks, while superficially similar, embody different approaches. Sesame, motivated by modeling and design-space exploration, uses evolutionary algorithms for mapping. MAPS, being a compiler framework, uses simple and fast heuristics instead. In this work we highlight the value of common abstractions, such as KPNs and traces, as a vehicle to enable comparisons between large independent frameworks. These types of comparisons are fundamental for advancing research in the area. At the same time, we illustrate how the lack of formalized models at the hardware level are an obstacle to achieving fair comparisons. Additionally, using a set of applications from the embedded systems domain, we observe that genetic algorithms tend to outperform heuristics by a factor between 1× and 5×, with notable exceptions. This performance comes at the cost of a longer computation time, between 0 and 2 orders of magnitude in our experiments.

Applying suitable application models is essential to achieve efficient execution of the applications, effective development process and assure application portability and reusability. We observe that execution environments and the cloud environment in particular, lack of tools that would make it more available from a programmer perspective. Complexity and variety of libraries and authentication methods do not correspond with simplistic functionality of those services. We approach this issue at several fields - workflow systems, domain specific languages and cloud computing. Our work focus on two points, optimizing existing application models by supplementing them with additional tools and providing new features, and develop new models that are based on our research on applications in the cloud environment.

Computational and storage tasks can nowadays be offloaded among data centers, in order to optimize costs and or performance. We set out to investigate what are the environmental effects, namely the total CO2 emission, of such offloading. We built models for the various components present in these offloading scenarios, and we incorporated these models into an online calculator available to users. Our online calculator determines the total CO2 emitted by performing computational or storage tasks at a local or remote data center, provided that the energy sources of the data centers and the network connecting them are known. The demonstration we propose will allow conference visitors to use our website/calculator to get a sense for the impact of offloading their storage and computational tasks.

Scientific applications are frequently modeled as a workflow that is executed under the control of a workflow management system. One crucial requirement during the execution is the validation of the generated results and the traceability of the experiment execution path. The automated tracking and storage of provenance information during workflow execution could satisfy this requirement. To collect provenance data using the Grid-enabled scientific workflow management system WS-VLAM, experimentation was made with two different implementations of the provenance concepts. The first one adopts the Open Provenance Model (OPM) as basis to represent, store, and share scientific experiments metadata using the Provenance Layer Infrastructure for e-Science Resources (PLIER). The second one is the history-tracing XML (HisT) which was developed for e-Business provenance. HisT provides a specific model to store provenance data within layered XML documents, whereby each layer is related to one individual workflow task. This paper explores these two provenance models by using an example workflow application and describes how they are integrated into WS-VLAM including implementation details of the provenance architecture. It finally gives a comparison of the two different approaches with a special regard to provenance for human actors.