AlgoDEEP
Algorithmic challenges for Data-intensivE
processing on Emerging computing Platforms
16-17 aprile 2010
Kickoff Meeting, Bertinoro
1
PRIN 2008: dati Area 9
Progetti cofinanziati:
103
Cofinanziamento medio: 107.700
Cofinanziamento min:
24.810
Cofinanziamento max:
181.608
16-17 aprile 2010
Kickoff Meeting, Bertinoro
2
Com’è andata a noi …
COFIN
COFIN
RICHIESTO ASSEGNATO
232.000
127.027
(54.7%)
MESI
UOMO
442
COFIN/MU PERSONE
287
61
COFIN/
PERSONA
2.082
Nota Illustrativa 18/12/1008: “Non potrà essere presa in
considerazione […] una riduzione degli obiettivi del progetto […]”
perché … ”La riduzione del cofinanziamento, in sede di
approvazione del progetto, sarà da porre in relazione
esclusivamente con costi ritenuti non congrui dai valutatori”
Costi ritenuti non congrui dai valutatori: nessuno.
16-17 aprile 2010
Kickoff Meeting, Bertinoro
3
Un po’ di nostra storia …
Cofin (Keuro)
16-17 aprile 2010
Kickoff Meeting, Bertinoro
4
TaskTree
CHALLENGE 1
Adaptive
Computations
Leader: C. Fantozzi
C1.1: Faulty memories
C1.2: Oblivious multicore computations
CHALLENGE 2
C2.1: Extraction of significant properties
Massive Data Analysis
and patterns
Leader: M. Patrignani
C2.2: Analysis of dynamic networks
CHALLENGE 3
C3.1: Design and maintainance of large
Empowering
networks
Computation on LargeC3.2: Computation and communication in
Scale Networks
large networks
Leader: F. Grandoni
16-17 aprile 2010
Kickoff Meeting, Bertinoro
5
C1: Adaptive Computations
Adaptivity: ability of reacting to changing
conditions.
It is needed, e.g.


to ensure correctness
Example: resiliency to hardware faults
to attain efficiency
Example: heterogeneous platforms
in grid/global/cloud computing
16-17 aprile 2010
Kickoff Meeting, Bertinoro
6
C1: Tasks
C1.1: Faulty Memories


Design of adaptive algorithms and data structures
that are resilient to memory faults
Is ”fault-obliviousness” (i.e., resiliency without
knowing a statistics of faults) possible?
C1.2: Oblivious Multicore Computations


How far optimal performance can be attained in
an oblivious fashion w.r.t. parallelism, memory
hierarchy, and communication?
Ultimate goal: a notion of ”machine obliviousness”
16-17 aprile 2010
Kickoff Meeting, Bertinoro
7
C1: Expected Results
C1.1: Faulty Memories
 M12: New computational models for faulty memories,
including fault-obliviousness. New resilient (possibly
fault-oblivious) algorithms and data structures
 M24: Experimental validation of the resilient algorithms
and data structures developed during the first year
C1.2: Oblivious Multicore Computations


M12: Unified computational model that accounts for
network locality, locality of reference, and parallelism,
as shaped in multicores
M24: Framework for the specification of machine-oblivious
algorithms. Machine-oblivious algorithms for basic primitives
16-17 aprile 2010
Kickoff Meeting, Bertinoro
8
C2: Massive Data Analysis
Large datasets


are found in biology, marketing, network
analysis, program analysis, etc
may be static or dynamic
Challenging tasks

extracting significant information (what is
significance?)

identifying clusters

understanding dynamics
16-17 aprile 2010
Kickoff Meeting, Bertinoro
9
C2: Tasks
C2.1: Extraction of Significant Properties & Patterns


DYNAMIC PROGRAM ANALYSIS: efficient techniques for
runtime invariant checking and error localization
PATTERN EXTRACTION FROM STATIC DATA:
characterization of statistical significance (applied to;
frequent itemsets mining); discovery of motifs in
genomic sequences
C2.2: Analysis of Dynamic Networks


ANALYSIS OF ROUTING AND TRAFFIC INFO: to extract
information about AS graphs dynamics, and clusters
VISUALIZATION TOOLS: dealing with endless streams of
data; hybrid visualization through clustering
16-17 aprile 2010
Kickoff Meeting, Bertinoro
10
C2: Expected Results
C2.1: Extraction of Significant Properties & Patterns


M12: Constraint-based framework for dynamic invariant checking
based on efficient incremental change propagation algorithms.
Statistical techniques to guide the mining of frequent itemsets.
Extraction of long motifs from genomic sequences.
M24: Efficient external-memory data structures for recording trails
of operations. Discovery of motifs with wildcards. Discovery of
permutation patterns.
C2.2: Analysis of Dynamic Networks


M12: Large repository of routing updates and RIB dumps.
Algorithms to indentify hot-spots, understand routing dynamics,
extract structural properties and clusters. Visualization of stream of
edges. Visualization of non-planar dense subgraphs and clusters.
M24: Usage of information gathered to optimize and reduce
instability of BGP and detecting causes of instability in real-time.
Implementation and experimental validation of clustering
algorithms. Tools to visualize clustered graphs and stream of edges.
algorithms for the visualization of non-planar networks.
16-17 aprile 2010
Kickoff Meeting, Bertinoro
11
C3: Computation on Large Networks
Analysis: structural properties of real-world
networks
Design: networks with complex constraints
Maintenance: algorithmic and visualization tools
for network monitoring and maintenance
Use: algorithms and data structures for efficient
computation and communication
16-17 aprile 2010
Kickoff Meeting, Bertinoro
12
C3: Tasks
C3.1: Design and Maintenance


NETWORK DESIGN: design and analysis in complex
scenarios
NETWORK MAINTAINANCE: Monitoring and maintenance
of large-scale heterogeneous networks
C3.2:Computation and Communication


EMPOWERING COMPUTATION: Space/network-efficient
algorithms for cloud computing
EMPOWERING COMMUNICATION: Efficient
communication primitives for routing/broadcasting
16-17 aprile 2010
Kickoff Meeting, Bertinoro
13
C3: Expected Results
C3.1: Design and Maintenance


M12: Multi-objective network design. Low-stretch routing with
limited node memory. Analysis of static wireless networks.
Techniques for real-time monitoring of traffic. Maintenance of tree
spanners under network failures.
M24: Stochastic network design and experimental validation of
developed algorithms. Near-optimal bandwidth usage with limited
node memory. Analysis of mobile wireless networks.
Implementation of real-time monitoring tools. Distributed
maintenance of robust spanners.
C3.2:Computation and Communication


M12: Service-oriented computing with outsourcing of computation.
Models for distributed/streaming computation, with applications to
cloud computing. Labeling schemes for routing/broadcasting.
Heuristics and visualization tools for stability check.
M24: Development of synopses. Primitives for processing massive
text collections. Experimental validation of labeling schemes.
Testing of heuristics for instability detection.
April 16-17,
16-17
aprile 2010
2010
AlgoDEEP
Kickoff Meeting,
KickoffBertinoro
Meeting
14
Units Involved
C1.1
Padova
Pisa
+
Roma 1
*
*
Roma 2
C1.2
C2.1
*
+
*
*
*
+
+
C2.2
Roma 3


C3.1
*
*
*
*
*
C3.2
+
*
*
*
*
*
The symbol
* denotes direct involvement
The symbol + denotes a mere interest
16-17 aprile 2010
Kickoff Meeting, Bertinoro
15
Da proposal:
1. Kickoff meeting 
2. Meeting fine I anno ?
3. Meeting finale
4. Sito web
(verona.dei.unipd.it/~prin08)
16-17 aprile 2010
Kickoff Meeting, Bertinoro
16
Honors
• F. Grandoni et al.:
Best Paper Award STOC2010
• F. Silvestri et al.:
Best Paper Award IPDPS 2010
 APPLAUSO
16-17 aprile 2010
Kickoff Meeting, Bertinoro
17
Pianificazione
• Sito web
(verona.dei.unipd.it/~prin08)
•
lucidi kickoff
• Rideterminazione dei Costi
•
Scadenza ufficiale 3/5/2010 ore 17
•
•
Scadenza nostra 28/4/2010
“ripartizione senza alcun vincolo”. In fase di esecuzione, eventuali
rimodulazioni delle spese senza richiesta di autorizzazione, non
devono superare il 20% di quanto deciso in fase di
rideterminazione
• Valutazione finale: occhio agli expected results
• Workshop tematici
• Varie ed eventuali
16-17 aprile 2010
Kickoff Meeting, Bertinoro
18
Pianificazione
16-17 aprile 2010
Kickoff Meeting, Bertinoro
19
KICKOFF Meeting
16-17 aprile 2010
Kickoff Meeting, Bertinoro
20