Graph Analysis & HPC Techniques for Realizing Urban OS
Download as pptx, pdf2 likes502 views
Urban Operating System is an advanced data and analytic platform to solve variety of social issues. This slide shows the concept of Urban OS.
More Related Content
What's hot (20)
Viewers also liked (20)
Similar to Graph Analysis & HPC Techniques for Realizing Urban OS (20)
Recently uploaded (20)
Graph Analysis & HPC Techniques for Realizing Urban OS
- 1. Graph Analysis & High-Performance Computing Techniques for Realizing Urban OS Katsuki Fujisawa Hisato P. Matsuo 0
- 2. Kyushu University in Ｆｕｋｕｏｋａ Katsuki Fujisawa Hisato Peter Matsuo Presenters 2014 Center of Innovation Project 1998 Received Ph.D. Full Professor, Institute of Mathematics for Industry (IMI), Kyushu University Joined IBM Research Fellow, Center for Co-Evolutional Social Systems, Kyushu University - Research Director of the JST CREST for Post-Peta HPC - Graph500 Winner / Green Graph500 3rd winner in 2014 - Memory system Architect for Storage subsystem - IaaS/PaaS product Consultant -> now Urban OS Designer Joined Kyushu-U as Full Professor Left IBM, Joined Kyushu-U 2022Now
- 3. Agenda Urban OS that realizes next generation Smart City Architecture and Infrastructure Software architecture and Analytic system Graph Analysis & HPC Summary and our goal
- 4. Urban Issues/Challenges ・Energy issues ・Environment, water, sanitation & hygiene ・Disaster control ・Population decline ・Low birth rate & rapid aging ・Urban concentration ・Traffic problems ・Means of mobility ・Information access ・Globalization ・Diversity ・Information divide ・Finance ・Industrial promotion ・Gov. administration ・Education/Welfare ・Innovation
- 5. Urban OS provides three Mobility’s Anyone can access … anytime, anywhere Urban OSPeople/Materials mobility on-demand and effective transportation Energy mobility secured energy supply Information mobility appropriate information
- 6. Three Mobility’s lead sustainable society People/Mate rial Mobility Information Mobility Energy Mobility Efficient & optimized Infrastructure Creative Community Efficient & flexible Energy
- 7. Agenda Urban OS that realizes next generation Smart City Architecture and Infrastructure Software architecture and Analytic system Graph Analysis & HPC Summary and our goal
- 8. Urban OS Functions Event secu- rity plan Complaint response Traffic information Urban OS Flexible energy demand response Effective eva- cuation plan Smart traffic control Traffic data Weather/ Disaster data Gov./Public data Energy data Person data Open Data Information Feedback Co-evolutional Society Cross-utilization of various data Automatic optimization, control & bottleneck analysis Open platform for social/public/commercial applications Big data / Open data Sensor Network Application Service Optimization/Analytic Data Store Data Open platform for advanced urban services
- 10. Data for Person/Traffic/City plan optimization
- 11. Data Example : Public Open data Government Open data in Fukuoka city Map Mashup Utilized ApplicationsData Catalogue Dataset Search • Open data – Census – Statistics – Facilities – Report – others • Provided as: – CSV – PDF – … then • Transform to – RDF format – Linked data
- 12. Data Example : Sensor Poles 14 Poles in the campus Sensor Network in Kyushu University Network Camera WiFi Access Point Temp/Humid Sensor IC card Reader Laser Range Finder Gateway • Analyze – Campus people flow • Connect to – smartphones – with ID badge authentication traces
- 13. Data for Energy optimization
- 14. Data Example : Campus Energy Monitor Hydrogen Society model case in Kyushu University Hydrogen StationLarge scale Fuel Cell • Research how we utilize hydrogen in our society. – using renewable energy – using vehicle energy
- 15. How data are processed in Urban OS
- 16. Agenda Urban OS that realizes next generation Smart City Architecture and Infrastructure Software architecture and Analytic system Graph Analysis & HPC Summary and our goal
- 17. Required Technology for Urban OS
- 18. Cyber Space Urban OS Optimization Layer Long term oriented analysis (Quarter / Year) Compute complex calculation in advance, Apply to plan / design Large computation Mid-level Analysis Layer Micro Analysis Layer Real World Real World Modeling Real World Optimization / Simulation Feedback/Control Real World Macro Analysis Layer Mid term oriented analysis (Day / Week) Adaptive plan / design revision depending on events / condition changes Short term oriented analysis (real-time) Compute “present” condition continuously, Respond to emergency situations Small computation Implement individualized analysis algorithm for long/mid/short term analysis layers Model various Real World facts, Analyze on Cyber Space, Feedback to Real World
- 19. Cyber Space Urban OS supported Society -Traffic- Real-time Calculation On-Demand Calculation Deep Calculation Macro Analysis Layer Mid-level Analysis Layer Micro Analysis Layer Traffic network/ facility distribution Apply to City Plan Roads / Traffic / Pedestrian / Vehicles Bottleneck analysis Optimization calculation Quickest Flow calculation Congestion-adaptive real- time evacuation guidance Real World Real World Modeling Real World Optimization / Simulation Feedback/Control Real World Long Term Mid Term Short Term Adaptive traffic scheduling per events “Present” crowd and facilities City Community Vicinity Bottleneck analysis Optimization calculation
- 20. Urban OS supported Society -Energy- Real-time Calculation On-Demand Calculation Deep Calculation Energy infra facility distribution Apply to Smart Grid / City Energy Plan Area energy status facility distribution Hydrogen utilized area energy ecosystem Demand Supply analysis optimization Flexible energy operation using mobile energy objects for an emergency “Present” energy status / distribution Macro Analysis Layer Mid-level Analysis Layer Micro Analysis Layer Long Term Mid Term Short Term City Community Vicinity Cyber SpaceReal World Real World Modeling Real World Optimization / Simulation Feedback/Control Real World Bottleneck analysis Optimization calculation Bottleneck analysis Optimization calculation
- 21. Agenda Urban OS that realizes next generation Smart City Architecture and Infrastructure Software architecture and Analytic system Graph Analysis & HPC Summary and our goal
- 22. Emerged Graph Analysis • The extremely large-scale graphs that have recently emerged in various application fields – US Road network : 58 million edges – Twitter fellow-ship : 1.47 billion edges – Neuronal network : 100 trillion edges 89 billion nodes & 100 trillion edges Neuronal network @ Human Brain Project Cyber-security Twitter US road network 24 million nodes & 58 million edges 15 billion log entries / day Social network • Fast and scalable graph processing by using HPC 61.6 million nodes & 1.47 billion edges
- 23. The size of graphs 20 25 30 35 40 45 15 20 25 30 35 40 45 log2(m) log2(n) USA-road- d.NY.gr USA-road-d.LKS.gr USA-road-d.USA.gr Human Brain Project Graph500 (Toy) Graph500 (Mini) Graph500 (Small) Graph500 (Medium) Graph500 (Large) Graph500 (Huge) 1 billion nodes 1 trillion nodes 1 billion edges 1 trillion edges Symbolic Network USA Road Network Twitter (tweets/day) No. of nodes No. of edges K computer: 65536nodes Graph500: 17977 GTEPS
- 24. Extremely Large-scale Graph Analysis System ‘03 ‘05 ‘07 ‘09 ‘11 Data Source Data Source Large Sensor • Monitoring Data • Smart Grid • Traffic Transportation • SNS (Twitter) Visualization Indexing Centrality Clustering Shortest Path Connected Component Page Rank Mathematical Optimization Multi-thread Library Streaming Processing System Graph Processing Graph Analysis and Optimization Library Post-petascale or Exascale Supercomputer Hierarchical Graph Store Protection against disasters Traffic・Transportation Network Large Scale Social NetworksSmart Grid
- 25. Our achievements : Graph500 ×3.25 K computer SGI UV2000 TSUBAME 2.5 #3 #4 #3 FX10 TSUBAME-KFC #1 #4 #4 #4 CPU only GPU CPU only 4-way Xeon server
- 26. Our achievements : Graph500
- 27. Graph Analysis in Urban Society A traffic infrastructure is represented as a graph Road network / Transportation network Person flow / Vehicle flow is superimposed on a network An energy infrastructure are represented as a graph Power grid / gas pipeline / hydrogen Supply-Demand and environmental data are superimposed on an energy network Urban graph data will be calculated. Optimization with Graph Analysis City level : very large scaled Community : large scaled Local : realtime with contraction Algorithm / Hardware resource should be appropriately selected
- 28. Technology used in Macro Analysis Layer
- 29. Technology used in Mid-level Analysis Layer
- 30. Betweenness Centrality Highway Bridge • Definition : # of (s,t)-shortest paths : # of (s,t)-shortest paths passing throw v Osaka road network 13,076 vertices and 40,528 edges High score vertex/edge ＝ Important place c.g.) Highway, Bridge • BFS => one-to-all • <#vertices> times BFS => all-to-all • BC requires the all-to-all shortest paths • BC measures important vertices and edges without coordinates => 13,076 times BFS computations
- 31. Fukuoka road network # of nodes: 314,571 # of edgs 694,906 Graph Computation time 2m 30s (180 CPU cores) Betweenness centrality HP ProLiant m710 Server cartridge
- 32. Technology used in Micro Analysis Layer
- 33. Real-time Emergency Evacuation Planning • catastrophic disasters by massive earthquakes are increasing in the world, and disaster management is required more than ever 0 20 40 60 80 100 0 1 2 3 4 5 6 7 8 9 Evacuated(%) Elapsed time flow quickest flow universally quickest flow Quickest Evacuationmaximizes the cumulative number of evacuees Cumulativenumberofevacuees(%) Universally Quickest Flow(UQF) Not simulation But Optimization Problem UQF simultaneously maximizes the cumulative number of evacuees at an arbitrary time. Evacuation planning can be reduced to UQF of a given dynamic network. 0% 100% Utilization Ratio of Refuge (%)
- 34. Agenda Urban OS that realizes next generation Smart City Architecture and Infrastructure Software architecture and Analytic system Graph Analysis & HPC Summary and our goal
- 35. Where we are Evaluation of regulatory policy for a new technology through science, technology and innovation policy perspective. Creation of smart and multimodal mobility systems. Development of energy economics model for consumers taking bounded rationality behavior in consideration. Urban OS Application Device/Data Development of durable, efficient and high performance solid oxide / polymer electrolyte fuel cells. Development of next generation display devices using OLED, which can facilitate communication exchange for all people anytime, anywhere. Development of CPS (Cyber Physical System)-based urban OS, which manages, controls, and optimizes mobility of people and materials. Development of realistic analysis models for urban OS utilizing techniques developed by “math for industry”.
- 36. Our Goal Urban OS as an open platform of data aggregation big data / open data / sensor data / linked data Urban OS as an advanced optimization / analytic platform utilizing HPC based graph analysis experience Urban OS as an application platform to delightedly support start-ups.
- 37. Thank you!
Editor's Notes
- #18: 交通、物流やエネルギー最適化の社会の実現にあたり、都市OSのコアコンピタンスとして、 時間軸に応じた3層構造のアルゴリズムを実装します。 マクロ解析層では長期都市計画に類する計算。 中位解析層では数日、週、月単位での変化を反映する計算。 ミクロ解析層ではリアルタイムに変化を織り込み計算。
- #19: 交通、物流やエネルギー最適化の社会の実現にあたり、都市OSのコアコンピタンスとして、 時間軸に応じた3層構造のアルゴリズムを実装します。 マクロ解析層では長期都市計画に類する計算。 中位解析層では数日、週、月単位での変化を反映する計算。 ミクロ解析層ではリアルタイムに変化を織り込み計算。
- #20: 説明 九大COI が社会実装する都市OSは、Internet of Things 時代のビッグデータ、オープンデータを長期・中期・短期スパンで分析し最適化します。 実世界で生成される様々な情報をデータ化、サイバー空間でモデリングして分析と最適化、その結果を実社会にフィードバックし制御することにより、より住みよい社会を実現します。 分析・最適化は時間軸から対象となる期間を、長期・中期・短期の3つのレイヤーに分けます。 長期スパンでは、数か月、年単位でマクロ的分析を行います。計算量が大きく精緻な分析をオフラインで行います。設備の配置、交通計画など、都市計画に応用できます。 中期スパンでは、1日、1週間単位での分析を行います。イベントに応じた交通機関のダイヤ編成計画、天候に応じた混雑のない交通規制に応用できます。 短期スパンでは、リアルタイムでのミクロ的分析を行います。計算量が小さい分析をリアルタイムで連続的に行います。常に人の分布と避難所への最短ルートを計算し、災害時に瞬時に避難誘導することに応用できます。 - Kyushu University COI project is going to create the Urban OS that executes analytic and optimization of Bigdata/OpenData in a long term, mid term and short term operation. - In the Urban OS, various data from the real world are modeled and the cyber space retrieves the real world data, analyzes and optimizes. The computed data go back to the real world and our life will be improved. - The analytic and optimization function can be divided into three term-oriented layers, long term, mid term and short term. - Long term layer is for a macro level analysis, in months or year long operation. The calculation is done with larger data precisely as one-time analysis. This layer can be used for an urban plan of transportation and facilities. - Mid term layer is for days or weeks operation. This layer can be used for an adaptive transportation service plan. It can be also used for congestion-free traffic control corresponding to weather. - Short term layer is for a micro level analysis in realtime computing. Analysis is done continuously with rather small data. In this layer, an adaptive evacuation guidance can be done by computing shortest route to the nearest evacuation center from people distribution data at the all time.
- #21: この長期・中期・短期アーキテクチャーの考え方はエネルギーにも当てはまります。 長期スパンでは、交通網、重要施設の情報を元にした、水素ステーションの配置、発電所の配置、送電網設計などのエネルギーインフラ計画策定に応用できます。 中期スパンでは、移動型水素ステーションや週間天候情報を基にしたCEMSなどの中期エネルギー計画の策定に応用できます。 短期スパンでは、需給状態をリアルタイムに分析し、BEMS、FEMS、HEMSなどのローカルEMS最適化に応用します。 - The 3-layer architecture can be extended to the energy world. - Long term layer is used for an energy infrastructure plan such as hydragen station or power plant placement and power grid design using other urban system information. - Mid term layer is used for a CEMS energy plan using information of mobile hydrogen stations or weekly weather information. - Short term layer is used for local area energy management system such as BEMS, FEMS and HEMS with continuous, realtime analysis of demand and supply.
- #23: This is a background of our projects I think the extremely large-scale …. Fields For example, this is a United states road network graph. This graph 24 million nodes and 58 million edges. And social network twitter fellowship graph has 1.47 billion edges Neuronal network has 100 trillion edges
- #25: Hierarchal Graph Store: Utilizing emerging NVM devices as extended semi-external memory volumes for processing extremely large-scale graphs that exceed the DRAM capacity of the compute nodes Design highly efficient and scalable data offloading techniques, PGAS-based I/O abstraction schemes, and optimized I/O interfaces to NVMs. Graph Analysis and Optimization Library: Perform graph analysis and search algorithms, such as the BFS kernel for Graph500, on multiple CPUs and GPUs. Implementations, including communication-avoiding algorithms and techniques for overlapping computation and communication, are needed for these libraries. Finally, we can make a BFS tree from an arbitrary node and find a shortest path between two arbitrary nods on extremely large-scale graphs with tens of trillions of nodes and hundreds of trillions of edges. Graph Processing and Visualization: We aim to perform an interactive operation for large-scale graphs with hundreds of million of nodes and tens of billion of edges.
- #29: この長期・中期・短期アーキテクチャーの考え方はエネルギーにも当てはまります。 長期スパンでは、交通網、重要施設の情報を元にした、水素ステーションの配置、発電所の配置、送電網設計などのエネルギーインフラ計画策定に応用できます。 中期スパンでは、移動型水素ステーションや週間天候情報を基にしたCEMSなどの中期エネルギー計画の策定に応用できます。 短期スパンでは、需給状態をリアルタイムに分析し、BEMS、FEMS、HEMSなどのローカルEMS最適化に応用します。 - The 3-layer architecture can be extended to the energy world. - Long term layer is used for an energy infrastructure plan such as hydragen station or power plant placement and power grid design using other urban system information. - Mid term layer is used for a CEMS energy plan using information of mobile hydrogen stations or weekly weather information. - Short term layer is used for local area energy management system such as BEMS, FEMS and HEMS with continuous, realtime analysis of demand and supply.
- #30: この長期・中期・短期アーキテクチャーの考え方はエネルギーにも当てはまります。 長期スパンでは、交通網、重要施設の情報を元にした、水素ステーションの配置、発電所の配置、送電網設計などのエネルギーインフラ計画策定に応用できます。 中期スパンでは、移動型水素ステーションや週間天候情報を基にしたCEMSなどの中期エネルギー計画の策定に応用できます。 短期スパンでは、需給状態をリアルタイムに分析し、BEMS、FEMS、HEMSなどのローカルEMS最適化に応用します。 - The 3-layer architecture can be extended to the energy world. - Long term layer is used for an energy infrastructure plan such as hydragen station or power plant placement and power grid design using other urban system information. - Mid term layer is used for a CEMS energy plan using information of mobile hydrogen stations or weekly weather information. - Short term layer is used for local area energy management system such as BEMS, FEMS and HEMS with continuous, realtime analysis of demand and supply.
- #33: この長期・中期・短期アーキテクチャーの考え方はエネルギーにも当てはまります。 長期スパンでは、交通網、重要施設の情報を元にした、水素ステーションの配置、発電所の配置、送電網設計などのエネルギーインフラ計画策定に応用できます。 中期スパンでは、移動型水素ステーションや週間天候情報を基にしたCEMSなどの中期エネルギー計画の策定に応用できます。 短期スパンでは、需給状態をリアルタイムに分析し、BEMS、FEMS、HEMSなどのローカルEMS最適化に応用します。 - The 3-layer architecture can be extended to the energy world. - Long term layer is used for an energy infrastructure plan such as hydragen station or power plant placement and power grid design using other urban system information. - Mid term layer is used for a CEMS energy plan using information of mobile hydrogen stations or weekly weather information. - Short term layer is used for local area energy management system such as BEMS, FEMS and HEMS with continuous, realtime analysis of demand and supply.