DAMA-UPC Public Seminars

Autor: Marta Mattoso
Data: February 22, 2010

Hora: 10:30

Lloc: Sala d'actes de la FIB

One of the main advantages of using a scientific workflow management system (SWfMS) to orchestrate data flows among scientific activities, is to control and register the whole workflow execution. The execution of activities within a workflow with high performance computing (HPC) presents challenges in SWfMS execution control. Remote execution control and provenance registry of the parallel activities is limited from the SWfMS side. This talk aims at showing a middleware solution as a bridge between SWfMS and HPC supporting workflow parallelization and provenance combined to MTC (Many Task Computing). It presents Hydra, a set of components to be included on the workflow specification of any SWMfS to control parallelization of activities as MTC. Hydra works in map/reduce style. Through Hydra's components, an MTC parallelization strategy can be registered, reused, and provenance may be uniformly gathered. Hydra aims at reducing the complexity involved in designing and managing activity/workflow parallel executions within scientific experiments. The main contributions of this work resides in helping the scientist in: (i) identifying parallel workflow activities in an abstract level, (ii) modeling workflow activities using MTC paradigm, (iii) submitting activities from the SWfMS to the distributed environment, (iv) steering by finding failures, detecting performance bottlenecks, monitoring processes status to let the SWfMS aware of the remote execution, and (v) gathering prospective and remote retrospective provenance data. We have evaluated Hydra in a Computational Fluid Dynamics (CFD) workflow and in a sensitivity analysis workflow for computing model constants in Large Eddy Simulation (LES) of turbulence. Experimental results show that a systematic approach for distributing parallel activities is viable, sparing scientist time and diminishing operational errors,with the additional benefits of distributed provenance support.

Autor: Arnau Padrol

Efficient graph clustering (or partitioning) has become a crucial operation for many different purposes, ranging from social network and web analysis to data graph mining or graph summarization. Although it has been shown that communities are usually overlapping, most of the literature related to community search on graphs or networks has focused on finding non-intersecting groupings of the nodes. In addition, taking into account the size of modern data sets, most of them typically rely on prohibitively expensive computations. In this paper, we present a novel approach to find communities in large graphs: we implicitly map the nodes into a virtual multidimensional vector space where communities can be easily represented and detected. Our proposal is not only effective at discovering the latent groups or communities defined by the link structure of a generic graph, but it also allows to detect overlapped communities in the data graph.

With this objective, we propose a new fitness function that evaluates the quality of a community without penalizing those nodes that are significantly linked to nodes in another community, as it happens in some previous proposals. With this, overlapping communities come to the surface naturally. In addition, our algorithm does not require to preassume a certain size or number for the communities, since this information has to be extracted from the graph structure itself. Even more important, we show that our proposal outperforms previous proposals in terms of execution time, specially for very large graphs like those representing social networks. Finally, our algorithm can be used globally to find all the communities in a graph, or locally to look for all the communities to which a given node belongs, without traversing the whole graph. Our experiments validate this approach in terms of quality of the results and performance. In addition, we show that our proposal is able to efficiently handle a large graph extracted from the Wikipedia containing more than 10^8 nodes and edges.