Big Data Tutorial on Mapping Big Data Applications

Big Data Tutorial on Mapping Big Data Applications

Big Data Tutorial on Mapping Big Data Applications to Clouds and HPC Keynote BigDat 2015: International Winter School on Big Data Tarragona, Spain, January 26-30, 2015 January 26 2015 Geoffrey Fox [email protected] http://www.infomall.org School of Informatics and Computing Digital Science Center Indiana University Bloomington 1/26/2015 1 Introduction These lectures weave together Data intensive applications and their key features Facets of Big Data Ogres Sports Analytics, Internet of Things and Image-based applications in detail

Parallelizing data mining algorithms (machine learning) HPC-ABDS (High Performance Computing Enhanced Apache Big Data Stack) General discussion and specific examples Hardware Architectures suitable for data intensive applications Cloud Computing and use of dynamic deployment DevOps to integrate with HPC 1/26/2015 2 Online Classes Big Data Applications & Analytics ~40 hours of video mainly discussing applications (The X in XInformatics or X-Analytics) in context of big data and clouds https://bigdatacoursespring2015.appspot.com/preview Big Data Open Source Software and Projects http ://bigdataopensourceprojects.soic.indiana.edu/ ~15 Hours of video discussing HPC-ABDS and use on FutureSystems in Big Data software Both divided into sections (coherent topics), units

(~lectures) and lessons (5-20 minutes where student is meant to stay awake 1/26/2015 3 Cloudmesh Resources Tutorials Main Home: http://introduction-to-cloud-computing-on-futuresystem s.readthedocs.org/en/latest/index.html Videos: http://introduction-to-cloud-computing-on-futuresystem s.readthedocs.org/en/latest/resources.html Cloudmesh Documentation with video clips: http://cloudmesh.github.io/introduction_to_cloud_com puting/class/i590.html There are a lot of Big Data and HPC Software systems in 17 (21) layers Build on do not compete with the 289 HPC-ABDS systems Kaleidoscope of (Apache) Big Data Stack (ABDS) and HPC Technologies January 14 2015

17) Workflow-Orchestration: Oozie, ODE, ActiveBPEL, Airavata, Pegasus, Kepler, Swift, Taverna, Triana, Trident, BioKepler, Galaxy, CrossIPython, Dryad, Naiad, Tez, Google FlumeJava, Crunch, Cascading, Scalding, e-Science Central, Azure Data Factory, NiFi (NSA) Cutting 16) Application and Analytics: Mahout , MLlib , MLbase, DataFu, mlpy, scikit-learn, CompLearn, Caffe, R, Bioconductor, ImageJ, pbdR, Functions Scalapack, PetSc, Azure Machine Learning, Google Prediction API, Google Translation API, Torch, Theano, H2O, Google Fusion Tables, 1) Message Oracle PGX, GraphLab, GraphX, CINET, NWB, Elasticsearch, IBM System G, IBM Watson, GraphBuilder(Intel), TinkerPop and Data 15A) High level Programming: Kite, Hive, HCatalog, Databee, Tajo, Pig, Phoenix, Shark, MRQL, Impala, Presto, Sawzall, Drill, Google Protocols: BigQuery (Dremel), Google Cloud DataFlow, Summingbird, SAP HANA, IBM META, HadoopDB, PolyBase Avro, Thrift, 15B) Frameworks: Google App Engine, AppScale, Red Hat OpenShift, Heroku, AWS Elastic Beanstalk, IBM BlueMix, Ninefold, Protobuf Aerobatic, Azure, Jelastic, Cloud Foundry, CloudBees, Engine Yard, CloudControl, appfog, dotCloud, Pivotal, OSGi, HUBzero, OODT 2) Distributed 14A) Basic Programming model and runtime, SPMD, MapReduce: Hadoop, Spark, Twister, Stratosphere (Apache Flink), Reef, Hama, Coordination: Giraph, Pregel, Pegasus 14B) Streams: Storm, S4, Samza, Google MillWheel, Amazon Kinesis, LinkedIn Databus, Facebook Scribe/ODS, Azure Stream Analytics Zookeeper, Giraffe, 13) Inter process communication Collectives, point-to-point, publish-subscribe: Harp, MPI, Netty, ZeroMQ, ActiveMQ, RabbitMQ, JGroups QPid, Kafka, Kestrel, JMS, AMQP, Stomp, MQTT, Azure Event Hubs, Amazon Lambda

Public Cloud: Amazon SNS, Google Pub Sub, Azure Queues 3) Security & 12) In-memory databases/caches: Gora (general object from NoSQL), Memcached, Redis (key value), Hazelcast, Ehcache, Infinispan Privacy: 12) Object-relational mapping: Hibernate, OpenJPA, EclipseLink, DataNucleus, ODBC/JDBC InCommon, 12) Extraction Tools: UIMA, Tika OpenStack 11C) SQL(NewSQL): Oracle, DB2, SQL Server, SQLite, MySQL, PostgreSQL, SciDB, Apache Derby, Google Cloud SQL, Azure SQL, Keystone, Amazon RDS, rasdaman, BlinkDB, N1QL, Galera Cluster, Google F1, Amazon Redshift, IBM dashDB LDAP, Sentry, 11B) NoSQL: HBase, Accumulo, Cassandra, Solandra, MongoDB, CouchDB, Lucene, Solr, Berkeley DB, Riak, Voldemort, Neo4J, Sqrrl Yarcdata, Jena, Sesame, AllegroGraph, RYA, Espresso, Sqrrl, Facebook Tao, Google Megastore, Google Spanner, Titan:db Public Cloud: Azure Table, Amazon Dynamo, Google DataStore 4) 11A) File management: iRODS, NetCDF, CDF, HDF, OPeNDAP, FITS, RCFile, ORC, Parquet Monitoring: 10) Data Transport: BitTorrent, HTTP, FTP, SSH, Globus Online (GridFTP), Flume, Sqoop Ambari, 9) Cluster Resource Management: Mesos, Yarn, Helix, Llama, Celery, HTCondor, SGE, OpenPBS, Moab, Slurm, Torque, Google Ganglia, Omega, Facebook Corona Nagios, Inca 8) File systems: HDFS, Swift, Cinder, Ceph, FUSE, Gluster, Lustre, GPFS, GFFS, Haystack, f4

Public Cloud: Amazon S3, Azure Blob, Google Cloud Storage 7) Interoperability: Whirr, JClouds, OCCI, CDMI, Libcloud, TOSCA, Libvirt 6) DevOps: Docker, Puppet, Chef, Ansible, Boto, Cobbler, Xcat, Razor, CloudMesh, Heat, Juju, Foreman, Rocks, Cisco Intelligent Automation for Cloud, Ubuntu MaaS, Facebook Tupperware, AWS OpsWorks, OpenStack Ironic 5) IaaS Management from HPC to hypervisors: Xen, KVM, Hyper-V, VirtualBox, OpenVZ, LXC, Linux-Vserver, VMware ESXi, 1/26/2015 vSphere, OpenStack, OpenNebula, Eucalyptus, Nimbus, CloudStack, VMware vCloud, Amazon, Azure, Google and other public5Clouds, Networking: Google Cloud DNS, Amazon Route 53 21 layers 289 Software Packages HPC and Data Analytics

Identify/develop parallel large scale data analytics data analytics library SPIDAL (Scalable Parallel Interoperable Data Analytics Library ) of similar quality to PETSc and ScaLAPACK which have been very influential in success of HPC for simulations Analyze Big Data applications to identify analytics needed and generate benchmark applications and characteristics (Ogres with facets) Analyze existing analytics libraries (in practice limit to some application domains and some general libraries) catalog library members available and performance Apache Mahout low performance and not many entries; R largely sequential and missing key algorithms; Apache MLlib just starting Identify range of big data computer architectures Analyze Big Data Software and identify software model HPC-ABDS (HPC Apache Big Data Stack) to allow interoperability (Cloud/HPC) and high performance merging HPC and commodity cloud software Design or identify new or existing algorithms including and assuming parallel implementation Many more data scientists than computational scientists so HPC implications of data analytics could be influential on simulation software and hardware Analytics and the DIKW Pipeline Data goes through a pipeline Raw data Data Information Knowledge Wisdom Decisions

Information Data Analytics Knowledge Information More Analytics Each link enabled by a filter which is business logic or analytics All filters are Analytics However I am most interested in filters that involve sophisticated analytics which require non trivial parallel algorithms Improve state of art in both algorithm quality and (parallel) performance See Apache Crunch or Google Cloud Dataflow supporting pipelined analytics And Pegasus, Taverna, Kepler from Grid community NIST Big Data Initiative Led by Chaitin Baru, Bob Marcus, Wo Chang

NBD-PWG (NIST Big Data Public Working Group) Subgroups & Co-Chairs There were 5 Subgroups Note mainly industry Requirements and Use Cases Sub Group Geoffrey Fox, Indiana U.; Joe Paiva, VA; Tsegereda Beyene, Cisco Definitions and Taxonomies SG Nancy Grady, SAIC; Natasha Balac, SDSC; Eugene Luster, R2AD Reference Architecture Sub Group Orit Levin, Microsoft; James Ketner, AT&T; Don Krapohl, Augmented Intelligence Security and Privacy Sub Group Arnab Roy, CSA/Fujitsu Nancy Landreville, U. MD Akhil Manchanda, GE Technology Roadmap Sub Group Carl Buffington, Vistronix; Dan McClary, Oracle; David Boyd, Data Tactics See http://bigdatawg.nist.gov/usecases.php And http://bigdatawg.nist.gov/V1_output_docs.php

9 Use Case Template 26 fields completed for 51 areas Government Operation: 4 Commercial: 8 Defense: 3 Healthcare and Life Sciences: 10 Deep Learning and Social Media: 6 The Ecosystem for Research: 4 Astronomy and Physics: 5 Earth, Environmental and Polar Science: 10 Energy: 1 10 51 Detailed Use Cases: Contributed July-September 2013 Covers goals, data features such as 3 Vs, software, hardware

26 Features for each use case http://bigdatawg.nist.gov/usecases.php https://bigdatacoursespring2014.appspot.com/course (Section 5) Biased to science Government Operation(4): National Archives and Records Administration, Census Bureau Commercial(8): Finance in Cloud, Cloud Backup, Mendeley (Citations), Netflix, Web Search, Digital Materials, Cargo shipping (as in UPS) Defense(3): Sensors, Image surveillance, Situation Assessment Healthcare and Life Sciences(10): Medical records, Graph and Probabilistic analysis, Pathology, Bioimaging, Genomics, Epidemiology, People Activity models, Biodiversity Deep Learning and Social Media(6): Driving Car, Geolocate images/cameras, Twitter, Crowd Sourcing, Network Science, NIST benchmark datasets The Ecosystem for Research(4): Metadata, Collaboration, Language Translation, Light source experiments Astronomy and Physics(5): Sky Surveys including comparison to simulation, Large Hadron

Collider at CERN, Belle Accelerator II in Japan Earth, Environmental and Polar Science(10): Radar Scattering in Atmosphere, Earthquake, Ocean, Earth Observation, Ice sheet Radar scattering, Earth radar mapping, Climate simulation datasets, Atmospheric turbulence identification, Subsurface Biogeochemistry (microbes to watersheds), AmeriFlux and FLUXNET gas sensors 11 Energy(1): Smart grid Application Example Montage Table 4: Characteristics of 6 Distributed Applications Execution Unit Communication Coordination Execution Environment Multiple sequential and parallel executable Multiple concurrent parallel executables Multiple seq. and parallel executables Files

Pub/sub Dataflow and events Climate Prediction (generation) Climate Prediction (analysis) SCOOP Multiple seq. & parallel executables Files and messages Multiple seq. & parallel executables Files and messages

MasterWorker, events Dataflow Coupled Fusion Multiple executable NEKTAR ReplicaExchange Multiple Executable Stream based Files and messages Stream-based Dataflow (DAG) Dataflow

Dataflow Dataflow Dynamic process creation, execution Co-scheduling, data streaming, async. I/O Decoupled coordination and messaging @Home (BOINC) Dynamics process creation, workflow execution Preemptive scheduling, reservations Co-scheduling, data streaming, async I/O Part of Property Summary Table 12 51 Use Cases: What is Parallelism Over?

People: either the users (but see below) or subjects of application and often both Decision makers like researchers or doctors (users of application) Items such as Images, EMR, Sequences below; observations or contents of online store Images or Electronic Information nuggets EMR: Electronic Medical Records (often similar to people parallelism)

Protein or Gene Sequences; Material properties, Manufactured Object specifications, etc., in custom dataset Modelled entities like vehicles and people Sensors Internet of Things Events such as detected anomalies in telescope or credit card data or atmosphere (Complex) Nodes in RDF Graph Simple nodes as in a learning network Tweets, Blogs, Documents, Web Pages, etc. And characters/words in them Files or data to be backed up, moved or assigned metadata Particles/cells/mesh points as in parallel simulations 13 Features of 51 Use Cases I PP (26) All Pleasingly Parallel or Map Only MR (18) Classic MapReduce MR (add MRStat below for full count) MRStat (7) Simple version of MR where key computations are simple reduction as found in statistical averages such as histograms and averages MRIter (23) Iterative MapReduce or MPI (Spark, Twister) Graph (9) Complex graph data structure needed in analysis Fusion (11) Integrate diverse data to aid discovery/decision making; could involve sophisticated algorithms or could just be a portal

Streaming (41) Some data comes in incrementally and is processed this way Classify (30) Classification: divide data into categories S/Q (12) Index, Search and Query Features of 51 Use Cases II CF (4) Collaborative Filtering for recommender engines LML (36) Local Machine Learning (Independent for each parallel entity) application could have GML as well GML (23) Global Machine Learning: Deep Learning, Clustering, LDA, PLSI, MDS, Large Scale Optimizations as in Variational Bayes, MCMC, Lifted Belief Propagation, Stochastic Gradient Descent, L-BFGS, Levenberg-Marquardt . Can call EGO or Exascale Global Optimization with scalable parallel algorithm Workflow (51) Universal GIS (16) Geotagged data and often displayed in ESRI, Microsoft Virtual Earth, Google Earth, GeoServer etc. HPC (5) Classic large-scale simulation of cosmos, materials, etc. generating (visualization) data Agent (2) Simulations of models of data-defined macroscopic entities represented as agents

6 Data Analysis Architectures Difficult to parallelize asynchronous parallel Graph Algorithms Classic Hadoop in classes 1) 2) but not clearly best in class 1) (6) Shared memory Map Communicates Shared Memory Map & Communicate Many Task) (1) Map Only (2) Classic MapReduce Input Input

(3) Iterative Map Reduce (4) Point to Point or or Map-Collective Map-Communication Input maps brokers map map map Iterations (5) Map Streaming Local reduce Output

PP BLAST Analysis Local Machine Learning Pleasingly Parallel MR MRStat High Energy Physics (HEP) Histograms Web search reduce MRIter Expectation maximization Clustering Linear Algebra, PageRank Recommender Engines

MapReduce and Iterative Extensions (Spark, Twister) Harp Enhanced Hadoop Graph, HPC Graph Streaming Events Classic MPI PDE Solvers and Particle Dynamics Graph Streaming images from Synchrotron sources, Telescopes, IoT MPI, Giraph

Apache Storm Maps are Bolts 13 Image-based Use Cases 13-15 Military Sensor Data Analysis/ Intelligence PP, LML, GIS, MR 7:Pathology Imaging/ Digital Pathology: PP, LML, MR for search becoming terabyte 3D images, Global Classification 18&35: Computational Bioimaging (Light Sources): PP, LML Also materials 26: Large-scale Deep Learning: GML Stanford ran 10 million images and 11 billion parameters on a 64 GPU HPC; vision (drive car), speech, and Natural Language Processing 27: Organizing large-scale, unstructured collections of photos: GML Fit position and camera direction to assemble 3D photo ensemble 36: Catalina Real-Time Transient Synoptic Sky Survey (CRTS): PP, LML followed by classification of events (GML) 43: Radar Data Analysis for CReSIS Remote Sensing of Ice Sheets: PP, LML to identify glacier beds; GML for full ice-sheet 44: UAVSAR Data Processing, Data Product Delivery, and Data Services: PP to find slippage from radar images 45, 46: Analysis of Simulation visualizations: PP LML ?GML find paths, classify orbits, classify patterns that signal earthquakes, instabilities, climate, turbulence Internet of Things and Streaming Apps

It is projected that there will be 24 (Mobile Industry Group) to 50 (Cisco) billion devices on the Internet by 2020. The cloud natural controller of and resource provider for the Internet of Things. Smart phones/watches, Wearable devices (Smart People), Intelligent River Smart Homes and Grid and Ubiquitous Cities, Robotics. Majority of use cases are streaming experimental science gathers data in a stream sometimes batched as in a field trip. Below is sample 10: Cargo Shipping Tracking as in UPS, Fedex PP GIS LML 13: Large Scale Geospatial Analysis and Visualization PP GIS LML 28: Truthy: Information diffusion research from Twitter Data PP MR for Search, GML for community determination 39: Particle Physics: Analysis of LHC Large Hadron Collider Data: Discovery of Higgs particle PP Local Processing Global statistics 50: DOE-BER AmeriFlux and FLUXNET Networks PP GIS LML 18 51: Consumption forecasting in Smart Grids PP GIS LML Global Machine Learning aka EGO Exascale Global Optimization Typically maximum likelihood or 2 with a sum over the N data items documents, sequences, items to be sold, images etc. and often links (point-pairs).

Usually its a sum of positive numbers as in least squares Covering clustering/community detection, mixture models, topic determination, Multidimensional scaling, (Deep) Learning Networks PageRank is just parallel linear algebra Note many Mahout algorithms are sequential partly as MapReduce limited; partly because parallelism unclear MLLib (Spark based) better SVM and Hidden Markov Models do not use large scale parallelization in practice? Some overlap/confusion with with graph analytics Data Gathering, Storage, Use 10 Bob Marcus Data Processing Use Cases 1) Multiple users performing interactive queries and updates on a database with basic availability and eventual consistency (BASE = (Basically Available, Soft state, Eventual consistency) as opposed to ACID = (Atomicity, Consistency, Isolation, Durability) ) 2) Perform real time analytics on data source streams and notify users when specified events occur 3) Move data from external data sources into a highly horizontally scalable data store, transform it using highly horizontally scalable processing (e.g. Map-Reduce), and

return it to the horizontally scalable data store (ELT Extract Load Transform) 4) Perform batch analytics on the data in a highly horizontally scalable data store using highly horizontally scalable processing (e.g MapReduce) with a user-friendly interface (e.g. SQL like) 5) Perform interactive analytics on data in analytics-optimized database 6) Visualize data extracted from horizontally scalable Big Data store 7) Move data from a highly horizontally scalable data store into a traditional Enterprise Data Warehouse (EDW) 8) Extract, process, and move data from data stores to archives 9) Combine data from Cloud databases and on premise data stores for analytics, data mining, and/or machine learning 10) Orchestrate multiple sequential and parallel data transformations and/or analytic processing using a workflow manager 2. Perform real time analytics on data source streams and notify users when specified events occur Specify filter Filter Identifying Events Streaming Data Streaming Data Streaming Data Post Selected

Events Fetch streamed Data Posted Data Identified Events Archive Repository Storm, Kafka, Hbase, Zookeeper 5. Perform interactive analytics on data in analytics-optimized database Mahout, R Hadoop, Spark, Giraph, Pig Data Storage: HDFS, Hbase Data, Streaming, Batch .. 5A. Perform interactive analytics on observational scientific data Science Analysis Code,

Mahout, R Grid or Many Task Software, Hadoop, Spark, Giraph, Pig Data Storage: HDFS, Hbase, File Collection Direct Transfer Streaming Twitter data for Social Networking Record Scientific Data in field Transport batch of data to primary analysis data system Local Accumulate and initial computing NIST examples include LHC, Remote Sensing, Astronomy and Bioinformatics Big Data Patterns the Ogres

Distributed Computing Practice for Large-Scale Science & Engineering S. Jha, M. Cole, D. Katz, O. Rana, M. Parashar, and J. Weissman, Characteristics of 6 Distributed Applications NOTE DATAFLOW Work ofExecution Unit Application Example Montage Communication Coordination Execution Environment Dynamic process creation, execution Co-scheduling, data streaming, async. I/O Decoupled coordination and messaging Multiple sequential Files

and parallel executable Multiple concurrent Stream based parallel executables Multiple seq. and Pub/sub parallel executables Dataflow (DAG) Dataflow Climate Prediction (generation) Multiple seq. & parallel Files and executables messages MasterWorker, events @Home (BOINC)

Climate Prediction (analysis) Multiple seq. & parallel executables Files and messages Dataflow Dynamics process creation, workflow execution Files and messages Stream-based Dataflow Preemptive scheduling,

reservations Co-scheduling, data streaming, async I/O NEKTAR ReplicaExchange SCOOP Multiple Executable Coupled Fusion Multiple executable Dataflow and events Dataflow 10 Security & Privacy Use Cases

Consumer Digital Media Usage Nielsen Homescan Web Traffic Analytics Health Information Exchange Personal Genetic Privacy Pharma Clinic Trial Data Sharing Cyber-security Aviation Industry Military - Unmanned Vehicle sensor data Education - Common Core Student Performance Reporting 7 Computational Giants of NRC Massive Data Analysis Report http://www.nap.edu/catalog.php?record_id=18374

1) 2) 3) 4) 5) 6) 7) G1: G2: G3: G4: G5: G6: G7: Basic Statistics e.g. MRStat Generalized N-Body Problems Graph-Theoretic Computations Linear Algebraic Computations Optimizations e.g. Linear Programming Integration e.g. LDA and other GML Alignment Problems e.g. BLAST

Would like to capture essence of these use cases small kernels, mini-apps Or Classify applications into patterns Section 5 of my class https://bigdatacoursespring2014.appspot.com/preview classifies 51 use cases with ogre facets HPC Benchmark Classics Linpack or HPL: Parallel LU factorization for solution of linear equations NPB version 1: Mainly classic HPC solver kernels MG: Multigrid CG: Conjugate Gradient FT: Fast Fourier Transform IS: Integer sort EP: Embarrassingly Parallel BT: Block Tridiagonal SP: Scalar Pentadiagonal LU: Lower-Upper symmetric Gauss Seidel 13 Berkeley Dwarfs 1) Dense Linear Algebra

2) Sparse Linear Algebra 3) Spectral Methods 4) N-Body Methods 5) Structured Grids 6) Unstructured Grids 7) MapReduce 8) Combinational Logic 9) Graph Traversal 10)Dynamic Programming 11)Backtrack and Branch-and-Bound 12)Graphical Models 13)Finite State Machines First 6 of these correspond to Colellas original. Monte Carlo dropped. N-body methods are a subset of Particle in Colella. Note a little inconsistent in that MapReduce is a programming model and spectral method is a numerical method. Need multiple facets!

Facets of the Ogres Introducing Big Data Ogres and their Facets I Big Data Ogres provide a systematic approach to understanding applications, and as such they have facets which represent key characteristics defined both from our experience and from a bottomup study of features from several individual applications. The facets capture common characteristics (shared by several problems)which are inevitably multi-dimensional and often overlapping. Ogres characteristics are cataloged in four distinct dimensions or views. Each view consists of facets; when multiple facets are linked together, they describe classes of big data problems represented as an Ogre. Instances of Ogres are particular big data problems A set of Ogre instances that cover a rich set of facets could form a benchmark set Ogres and their instances can be atomic or composite Introducing Big Data Ogres and their Facets II Ogres characteristics are cataloged in four distinct dimensions or views. Each view consists of facets; when multiple facets are linked together, they describe classes of big data problems represented as an Ogre. One view of an Ogre is the overall problem architecture which is naturally related to the machine architecture needed to support data

intensive application while still being different. Then there is the execution (computational) features view, describing issues such as I/O versus compute rates, iterative nature of computation and the classic Vs of Big Data: defining problem size, rate of change, etc. The data source & style view includes facets specifying how the data is collected, stored and accessed. The final processing view has facets which describe classes of processing steps including algorithms and kernels. Ogres are specified by the particular value of a set of facets linked from the different views. Facets of the Ogres Meta or Macro Aspects: Problem Architecture Problem Architecture View of Ogres (Meta or MacroPatterns) i. Pleasingly Parallel as in BLAST, Protein docking, some (bio-)imagery including Local Analytics or Machine Learning ML or filtering pleasingly parallel, as in bio-imagery, radar images (pleasingly parallel but sophisticated local analytics) ii. Classic MapReduce: Search, Index and Query and Classification algorithms like collaborative filtering (G1 for MRStat in Features, G7) iii. Map-Collective: Iterative maps + communication dominated by collective operations as

in reduction, broadcast, gather, scatter. Common datamining pattern iv. Map-Point to Point: Iterative maps + communication dominated by many small point to point messages as in graph algorithms v. Map-Streaming: Describes streaming, steering and assimilation problems vi. Shared Memory: Some problems are asynchronous and are easier to parallelize on shared rather than distributed memory see some graph algorithms vii. SPMD: Single Program Multiple Data, common parallel programming feature viii. BSP or Bulk Synchronous Processing: well-defined compute-communication phases ix. Fusion: Knowledge discovery often involves fusion of multiple methods. x. Dataflow: Important application features often occurring in composite Ogres xi. Use Agents: as in epidemiology (swarm approaches) xii. Workflow: All applications often involve orchestration (workflow) of multiple components Note problem and machine architectures are related Facets in the Execution Features Views i. ii. iii. One View of Ogres has Facets that are

micropatterns or Execution Features Performance Metrics; property found by benchmarking Ogre Flops per byte; memory or I/O Execution Environment; Core libraries needed: matrix-matrix/vector algebra, conjugate gradient, reduction, broadcast; Cloud, HPC etc. iv. Volume: property of an Ogre instance v. Velocity: qualitative property of Ogre with value associated with instance vi. Variety: important property especially of composite Ogres vii. Veracity: important property of mini-applications but not kernels viii. Communication Structure; Interconnect requirements; Is communication BSP, Asynchronous, Pub-Sub, Collective, Point to Point? ix. Is application (graph) static or dynamic? x. Most applications consist of a set of interconnected entities; is this regular as a set of pixels or is it a complicated irregular graph? xi. Are algorithms Iterative or not? xii. Data Abstraction: key-value, pixel, graph(G3), vector, bags of words or items xiii. Are data points in metric or non-metric spaces? xiv. Is algorithm O(N2) or O(N) (up to logs) for N points per iteration (G2) Facets of the Ogres Data Source and Style Aspects

Data Source and Style View of Ogres I i. SQL NewSQL or NoSQL: NoSQL includes Document, Column, Key-value, Graph, Triple store; NewSQL is SQL redone to exploit NoSQL performance ii. Other Enterprise data systems: 10 examples from NIST integrate SQL/NoSQL iii. Set of Files or Objects: as managed in iRODS and extremely common in scientific research iv. File systems, Object, Blob and Data-parallel (HDFS) raw storage: Separated from computing or colocated? HDFS v Lustre v. Openstack Swift v. GPFS v. Archive/Batched/Streaming: Streaming is incremental update of datasets with new algorithms to achieve real-time response (G7); Before data gets to compute system, there is often an initial data gathering phase which is characterized by a block size and timing. Block size varies from month (Remote Sensing, Seismic) to day (genomic) to seconds or lower (Real time control, streaming) Data Source and Style View of Ogres II vi. Shared/Dedicated/Transient/Permanent: qualitative property of data; Other characteristics are needed for permanent

auxiliary/comparison datasets and these could be interdisciplinary, implying nontrivial data movement/replication vii. Metadata/Provenance: Clear qualitative property but not for kernels as important aspect of data collection process viii. Internet of Things: 24 to 50 Billion devices on Internet by 2020 ix. HPC simulations: generate major (visualization) output that often needs to be mined x. Using GIS: Geographical Information Systems provide attractive access to geospatial data Note 10 Bob Marcus (lead NIST effort) Use cases Facets of the Ogres Processing View Facets in Processing (run time) View of Ogres I i. Micro-benchmarks ogres that exercise simple features of hardware such as communication, disk I/O, CPU, memory performance ii. Local Analytics executed on a single core or perhaps node iii. Global Analytics requiring iterative programming models (G5,G6) across multiple nodes of a parallel system iv. Optimization Methodology: overlapping categories i.

ii. iii. iv. v. vi. vii. v. Nonlinear Optimization (G6) Machine Learning Maximum Likelihood or 2 minimizations Expectation Maximization (often Steepest descent) Combinatorial Optimization Linear/Quadratic Programming (G5) Dynamic Programming Visualization is key application capability with algorithms like MDS useful but it itself part of mini-app or composite Ogre vi. Alignment (G7) as in BLAST compares samples with repository Facets in Processing (run time) View of Ogres II vii. Streaming divided into 5 categories depending on event size and synchronization and integration

Set of independent events where precise time sequencing unimportant. Time series of connected small events where time ordering important. Set of independent large events where each event needs parallel processing with time sequencing not critical Set of connected large events where each event needs parallel processing with time sequencing critical. Stream of connected small or large events to be integrated in a complex way. viii. Basic Statistics (G1): MRStat in NIST problem features ix. Search/Query/Index: Classic database which is well studied (Baru, Rabl tutorial) x. Recommender Engine: core to many e-commerce, media businesses; collaborative filtering key technology xi. Classification: assigning items to categories based on many methods MapReduce good in Alignment, Basic statistics, S/Q/I, Recommender, Calssification xii. Deep Learning of growing importance due to success in speech recognition etc.

xiii. Problem set up as a graph (G3) as opposed to vector, grid, bag of words etc. xiv. Using Linear Algebra Kernels: much machine learning uses linear algebra kernels Data Source and Style View 6 5 4 3 2 1 3 2 1 HDFS/Lustre/GPFS Files/Objects Enterprise Data Model SQL/NoSQL/NewSQL

4 Ogre Views and 50 Facets Pleasingly Parallel Classic MapReduce Map-Collective Map Point-to-Point Map Streaming Shared Memory Single Program Multiple Data Bulk Synchronous Parallel Fusion Problem Dataflow Agents Architecture Workflow View Geospatial Information System HPC Simulations Internet of Things

Metadata/Provenance Shared / Dedicated / Transient / Permanent Archived/Batched/Streaming 1 2 3 4 5 6 7 8 9 10 11 12 Execution View 1 2 3 4 5 6 7 8 9 10 11 12 13 14

= NN / = N Metric = M / Non-Metric = N Data Abstraction Iterative / Simple Regular = R / Irregular = I Dynamic = D / Static = S Communication Structure Veracity Variety Velocity Volume Execution Environment; Core libraries Flops/Byteper Byte; Memory I/O Flops Performance Metrics 7 Micro-benchmarks Local Analytics Global Analytics Optimization Methodology Processing View

8 Visualization Alignment Streaming Basic Statistics Search / Query / Index Recommender Engine Classification Deep Learning Graph Algorithms Linear Algebra Kernels 14 13 12 11 10 9 10 9 8 7 6 5

4 Benchmarks based on Ogres Analytics Core Analytics Ogre Instances (microPattern) I Map-Only Pleasingly parallel - Local Machine Learning MapReduce: Search/Query/Index Summarizing statistics as in LHC Data analysis (histograms) (G1) Recommender Systems (Collaborative Filtering) Linear Classifiers (Bayes, Random Forests) Alignment and Streaming (G7) Genomic Alignment, Incremental Classifiers Global Analytics Nonlinear Solvers (structure depends on objective function) (G5,G6) Stochastic Gradient Descent SGD (L-)BFGS approximation to Newtons Method Levenberg-Marquardt solver Core Analytics Ogre Instances (microPattern) II

Map-Collective (See Mahout, MLlib) (G2,G4,G6) Often use matrix-matrix,-vector operations, solvers (conjugate gradient) Outlier Detection, Clustering (many methods), Mixture Models, LDA (Latent Dirichlet Allocation), PLSI (Probabilistic Latent Semantic Indexing) SVM and Logistic Regression PageRank, (find leading eigenvector of sparse matrix) SVD (Singular Value Decomposition) MDS (Multidimensional Scaling) Learning Neural Networks (Deep Learning) Hidden Markov Models Core Analytics Ogre Instances (microPattern) III Global Analytics Map-Communication (targets for Giraph) (G3) Graph Structure (Communities, subgraphs/motifs, diameter, maximal cliques, connected components) Network Dynamics - Graph simulation Algorithms (epidemiology) Global Analytics Asynchronous Shared

Memory (may be distributed algorithms) Graph Structure (Betweenness centrality, shortest path) (G3) Linear/Quadratic Programming, Combinatorial Optimization, Branch and Bound (G5) Benchmarks across Facets Micro Benchmarks: SPEC, EnhancedDFSIO (HDFS), Terasort, Wordcount, Grep, MPI, Basic Pub-Sub . SQL and NoSQL Data systems, Search, Recommenders: TPC (-C to x HS for Hadoop), BigBench, Yahoo Cloud Serving, Berkeley Big Data, HiBench, BigDataBench, Cloudsuite, Linkbench Spatial Query: select from image or earth data Streaming: Gather in Pub-Sub(Kafka) + Process (Apache Storm) solution (e.g. gather tweets, Internet of Things); ? BGBenchmark; need examples of 5 subclasses Pleasingly parallel (Local Analytics): as in initial steps of LHC, Astronomy, Pathology, Bioimaging (differ in type of data analysis) Analytics: Select from those Ogres given earlier including Graph 500 entries Workflow and Composite (analytics on xSQL) linking above Algorithm

Problem Architecture View Applications Graph Analytics We can associate facets (numbered 1 for each view) with each potential benchmark. Then select benchmarks with unique facets. Community detection Social networks, webgraph Subgraph/motif finding Finding diameter 4, 7

Execution View Processing View Facets 9S, 10I, 11, 12G 3, 9ML, 13 Webgraph, biological/social networks 4, 7 9D, 10I, 12G 3, 9ML, 13 Social networks, webgraph 4, 7 9D, 10I, 12G 3, 9ML, 13 Clustering coeffi cient

Social networks 4, 7 9S, 10I, 11, 12G 3, 9ML, 13 Page rank Webgraph 3, 4, 7 9S, 10I, 11, 12V 3, 9ML, 12, 13 Maximal cliques Social networks, webgraph 4, 7

9D, 10I, 12G 3, 9ML, 13 Connected component Social networks, webgraph 4, 7 9D, 10I, 12G 3, 9ML, 13 Betweenness centrality Social networks 6 9D, 10I, 12G, 13N 9ML, 13 Shortest path

Social networks, webgraph 6 9D, 10I, 12G, 13N 9ML, 13 Spatial relationship based queries GIS/social networks/pathology informatics (add GIS execution view) Distance based queries 2 6 6 1 12P 2 Spatial clustering

3, 7, 8 12P 3, 9ML,EM Spatial mo deling 1 12P 2 vision/pathology 1 13M 2 1 13M

2, 9ML 1 13M 2, 9ML 3D image registration 1 13M 2, 9ML Object matching 1 13N 2, 9ML

3D feature extraction 1 13N 2, 9ML 3, 7, 8 9D, 10I, 11, 12V, 9ML, 9EM, 12 13M, 14N 3, 7, 8 9S, 10R, 11, 12BI, 9ML, 9EM, 12 13N, 14NN 3, 7, 8 9D, 10I(Elkan), 11, 9ML, 9EM 13M, 14N

Spatial Queries and Analytics Core Image Processing Image preprocessing Computer Object detection & segmentation informatics Image/object computation feature General Machine Learning DA Vector Clustering Accurate Clusters DA Non metric Clustering Accurate Clusters, Biology, Web Kmeans; Basic, Fuzzy and Elkan Fast Clustering

Levenberg-Marquardt Optimization Non-linear Gauss-Newton, use in 3, 7, 8 MDS 9D, 10R, 11, 12V, 9ML, 9NO, 9LS, 14NN 9EM, 12 DA, Weighted SMACOF MDS with general weights 3, 7, 8 9S, 10R, 11, 12BI, 9ML, 9NO, 9LS, 13N, 14NN 9EM, 12, 17 TFIDF Search Find nearest neighbors in document 1

corpus 9S, 10R, 12BI, 2, 9ML 9NMN, 14N Parallel Data Analytics Issues and examples Remarks on Parallelism I Most use parallelism over items in data set Entities to cluster or map to Euclidean space Except deep learning (for image data sets)which has parallelism over pixel plane in neurons not over items in training set as need to look at small numbers of data items at a time in Stochastic Gradient Descent SGD Need experiments to really test SGD as no easy to use parallel implementations tests at scale NOT done Maybe got where they are as most work sequential Maximum Likelihood or 2 both lead to structure like Minimize sum items=1N (Positive nonlinear function of unknown parameters for item i) All solved iteratively with (clever) first or second order approximation to shift in

objective function Sometimes steepest descent direction; sometimes Newton 11 billion deep learning parameters; Newton impossible Have classic Expectation Maximization structure Steepest descent shift is sum over shift calculated from each point SGD take randomly a few hundred of items in data set and calculate shifts over these and move a tiny distance 59 Remarks on Parallelism II Need to cover non vector semimetric and vector spaces for clustering and dimension reduction (N points in space) MDS Minimizes Stress (X) = i

Vector spaces have Euclidean distance and scalar products Algorithms can be O(N) and these are best for clustering but for MDS O(N) methods may not be best as obvious objective function O(N 2) Important new algorithms needed to define O(N) versions of current O(N 2) must work intuitively and shown in principle Note matrix solvers all use conjugate gradient converges in 5-100 iterations a big gain for matrix with a million rows. This removes factor of N in time complexity Ratio of #clusters to #points important; new ideas if ratio >~ 0.1 60 446K sequences ~100 clusters clean sample of 446K O(N2) green-green and purplepurple interactions have value but green-purple are wasted O(N2) interactions between green and purple clusters should be able to represent by centroids as in Barnes-Hut.

Hard as no Gauss theorem; no multipole expansion and points really in 1000 dimension space as clustered before 3D projection OctTree for 100K sample of Fungi We use OctTree for logarithmic interpolation (streaming data) 63 clean sample of 446K O(N2) green-green and purplepurple interactions have value but green-purple are wasted O(N2) interactions between green and purple clusters should be able to represent by centroids as in Barnes-Hut. Hard as no Gauss theorem; no multipole expansion and points

really in 1000 dimension space as clustered before 3D projection OctTree for 100K sample of Fungi We use OctTree for logarithmic interpolation (streaming data) 65 Protein Universe Browser (map big data to 3D to use GIS) for COG Sequences with a few illustrative biologically identified clusters 66 Heatmap of biology distance (NeedlemanWunsch) vs 3D Euclidean Distances If d a distance, so is f(d) for any monotonic f. Optimize choice of f 67 Algorithm Challenges

See NRC Massive Data Analysis report O(N) algorithms for O(N2) problems Parallelizing Stochastic Gradient Descent Streaming data algorithms balance and interplay between batch methods (most time consuming) and interpolative streaming methods Graph algorithms Machine Learning Community uses parameter servers; Parallel Computing (MPI) would not recommend this? Is classic distributed model for parameter service better? Apply best of parallel computing communication and load balancing to Giraph/Hadoop/Spark Are data analytics sparse?; many cases are full matrices BTW Need Java Grande Some C++ but Java most popular in ABDS, with Python, Erlang, Go, Scala (compiles to JVM) .. Lessons / Insights Proposed classification of Big Data applications with features generalized as facets and kernels for analytics

Data intensive algorithms do not have the well developed high performance libraries familiar from HPC Challenges with O(N2) problems Global Machine Learning or (Exascale Global Optimization) particularly challenging Develop SPIDAL (Scalable Parallel Interoperable Data Analytics Library) New algorithms and new high performance parallel implementations Integrate (dont compete) HPC with Commodity Big data (Google to Amazon to Enterprise/Startup Data Analytics) i.e. improve Mahout; dont compete with it Use Hadoop plug-ins rather than replacing Hadoop Enhanced Apache Big Data Stack HPC-ABDS has ~290 members with HPC opportunities at Resource management, Storage/Data, Streaming, Programming, monitoring, workflow layers.

Recently Viewed Presentations

  • SCIENCE AND INSTITUTIONS IN EU WATER MANAGEMENT Keith

    SCIENCE AND INSTITUTIONS IN EU WATER MANAGEMENT Keith

    The Water Framework Directive (i) Underlying principles and practice (i) Define water bodies Lakes - but also parts of river networks (But at what resolution? 5, 50, 500km2) Select a common basket of measures Hydromorphological, ecological and chemical indicators Hydromorphology...
  • The Lymphatic System - PC\|MAC

    The Lymphatic System - PC\|MAC

    Problems of the Lymphatic System. Tonsillitis. Inflammation or infection of the tonsils. Usually involves the pharyngeal and palatine tonsils. Symptoms include: throat pain, dysphagia, fever, white or yellowish spots on the tonsils, swollen lymph nodes near the mandible. Treatment: Antibiotics,...
  • The October Crisis - Ms. Cacilhas's Website

    The October Crisis - Ms. Cacilhas's Website

    The October Crisis Terrorism in Canada ... This was followed by a communiqué to the authorities that contained the kidnappers' demands that included the release of a number of convicted or detained terrorists and the broadcasting of the "FLQ Manifesto"....
  • Centru de expertiz pentru bolile rare  Expert RARE

    Centru de expertiz pentru bolile rare Expert RARE

    vorbim despre pacienti adulti constatăm prezența în fiecare grup a 1-2 persoane care dețin la momentul evaluării modalități de coping ce permit o buna adaptare la viața cu boli rare.
  • Rates of Reactions and Enzymes

    Rates of Reactions and Enzymes

    2) Enzymes are used in baby foods to "pre-digest" the proteins. 3) Enzymes are used to convert starch into sugar which can then be used in food. 4) Conversion of glucose into fructose - glucose and fructose are "isomers" (they...
  • Primer on Fourier Analysis

    Primer on Fourier Analysis

    Primer on Fourier Analysis Dana Moshkovitz Princeton University and The Institute for Advanced Study Fourier Analysis in Theoretical Computer Science Fourier Analysis in Theoretical Computer Science (Unofficial List) "The Fourier Magic" "something that looks scary to analyze" "bunch of (in)equalities"...
  • JAMA Facial Plastic Surgery Journal Club Slides: Local

    JAMA Facial Plastic Surgery Journal Club Slides: Local

    The highest density of musculocutaneous perforators from the facial artery is approximately 1.5 cm lateral to the oral commissure. For large medial cheek and cutaneous lip defects, the V-Y subcutaneous tissue pedicle island advancement flap is an important reconstructive technique....
  • Biology of Fishes ENV 422/NRE 422/EEB440

    Biology of Fishes ENV 422/NRE 422/EEB440

    Important considerations in fish locomotion. We can identify some fishes that are specialized for one trait, however, most fishes use a variety of modes of swimming and are locomotor generalists as opposed to locomotor specialists. Most fishes must cruise to...