60 %
40 %
Information about grass

Published on October 22, 2007

Author: Flemel


Flow Computation on Massive Grid Terrains:  Flow Computation on Massive Grid Terrains Helena Mitasova Dept. of Marine, Earth & Atmospheric Sciences, NCSU, USA*/terraflow Lars Arge Laura Toma Dept. of Computer Science Duke University, USA Modeling Flow on Grids :  Flow direction The direction water flows at a cell Flow Routing Compute flow direction for all cells in the terrain, including flat areas Flow accumulation value Total amount of water which flows through a cell per unit width of contour Flow is distributed according to the flow directions Flow Accumulation Compute flow accumulation values for all cells in the terrain Modeling Flow on Grids Massive Data :  Massive Data Remote sensing data available NASA-SRTM (whole Earth 5TB at 30m resolution) USGS (entire US at 10m resolution) LIDAR (1m resolution) Ex: Appalachian Mountains dataset 100m resolution (500MB) 30m resolution (5.5GB) 10m resolution (50GB) 1m resolution (5TB) Process Massive Data?:  Process Massive Data? GRASS r.watershed, ... Killed after running for 17 days on a 6700 x 4300 grid (approx 50 MB dataset) TARDEM flood, d8, aread8 Killed after running for 20 days on a 12000 x 10000 grid (appox 240 MB dataset) CPU utilization 5%, 3GB swap file ArcInfo flowdirection, flowaccumulation Can handle the 240MB dataset Doesn’t work for datasets bigger than 2GB TerraFlow:  TerraFlow Terraflow is our suite of programs for flow routing and flow accumulation on massive grids [ATV`00,AC&al`02] Flow routing and flow accumulation modeled as graph problems and solved in optimal I/O bounds Efficient 2-1000 times faster on very large grids than existing software Scalable 1 billion elements!! (>2GB data) Flexible Allows for both D8 and D-inf flow modeling*/terraflow r.terraflow:  r.terraflow Port of Terraflow into GRASS Preliminary results on Augment with additional features Output plateaus, depressions, tci, water outlet queries, watershed basins Comparison with GRASS flow routines r.watershed, r.flow, r.topidx, ... Performance results Outline:  Outline Scalability to large data Why standard programs are not in general scalable One approach to improve scalability I/O-efficient algorithms r.terraflow Algorithm outline Related work and programs Preliminary comparison and performance results Output illustration Scalability to Massive Data:  Scalability to Massive Data Why? Most GIS programss assume data fits in memory and minimize only CPU computation But..Massive data does not fit in main memory! OS places data on disk and moves data in and out of memory Data is moved in blocks Accessing the disk is 1000 times slower than accessing main memory when processing massive data disk I/O is the bottleneck, rather than CPU time! Scalability to Massive Data:  Scalability to Massive Data How? Local data accesses vs. scattered data accesses Example: reading an array from disk Array size N = 10 elements Disk block size = 2 elements Memory size = 4 elements (2 blocks) 1 2 10 9 5 6 3 4 8 7 1 5 2 6 3 8 9 4 7 10 Example:  Example r.watershed r.watershed –m el=elev_grid dir=dir_grid ac=accu_grid Running on a 500MHz PIII, 1GB RAM, FreeBSD On Hawaii dataset we let it run for 17 days in which it completed 65% However good the OS, it cannot change the data access pattern of the program!! TerraFlow Approach:  TerraFlow Approach Redesign the algorithm to be I/O-Efficient Block size is large! at least 8KB (32KB, 64KB) Compute on whole block while it is in memory Avoid loading a block each time Improved locality Speedup = block size I/O efficient algorithms measure of complexity: number of blocks transfered between main memory and disk*/terraflow r.terraflow outline:  r.terraflow outline Step 1: Flow routing Water flows downhill: SFD, MFD Compute SFD/MFD flow directions by inspecting 8 neighbor points Identify flat areas: plateaus and sinks*/terraflow Flow Routing on Flat Areas:  Flow Routing on Flat Areas …no obvious flow direction Plateaus Assign flow directions such that each cell flows towards the nearest spill point of the plateau Sinks Either catch the water inside the sink Assign flow directions towards the center of the sink Or route the water outside the sink using uphill flow directions Simulate flooding the terrain: sinks  plateaus Assign uphill flow directions on the original terrain by assigning downhill flow directions on the flooded terrain r.terraflow outline:  r.terraflow outline Step 2: Compute flow accumulation Water flows following the flow directions Goal: Compute the total amount of water through each grid cell Initially one unit of water in each grid cell Every cell distributes water to the neighbors pointed to by its flow direction(s) All these steps can be solved I/O-efficiently Flow routing: modeled as graph problems (breadth-first search, connected components, graph contraction) Flow accumulation: sweeping using an I/O-efficient priority queue Related Work:  Related Work TerraFlow’s emphasis Computational aspects, not modeling Flow modeling [O’Callaghan and Mark 1984] D8 method for flow accumulation [Jenson and Domingue 1988] General technique of flooding Software GRASS, ArcInfo,Tardem, Topaz, Tapes-G, RiverTools r.terraflow features:  r.terraflow features Input elevation grid Output flow direction grid SFD (D8) single flow directions MFD (Dinf) multiple flow directions flow accumulation grid Option to switch to SFD when flow value exceeds an user-defined threshold topographic convergence index (tci) grid plateau and depressions grid Slide17:  GRASS:>r.terraflow help Description: Flow computation for massive grids. Usage: r.terraflow [-sq] elev=name filled=name direction=name watershed=name accumulation=name tci=name [d8cut=value] [memory=value] [STREAM_DIR=name] [stats=name] Flags: -s SFD (D8) flow (default is MFD) -q Quiet Parameters: elev Input elevation grid filled Output (filled) elevation grid direction Output direction grid watershed Output watershed grid accumulation Output accumulation grid tci Output tci grid d8cut If flow accumulation is larger than this value it is routed using SFD (D8) direction (meaningfull only for MFD flow only). default: infinity memory Main memory size (in MB) default: 300 STREAM_DIR Location of intermediate STREAMs default: /var/tmp stats Stats file default: stats.outv*/terraflow GRASS Raster Flow Functions:  GRASS Raster Flow Functions r.watershed Most commonly used. Uses A* algorithm to determine flow of water. Ehlschlaeger, USACERL. Input: elevation, [..] Output: flow direction, flow accumulation, [waterhseds, stream segments, slope length, slope steepness] Flow direction grid equivalent to running r.drain for every cell on the grid Watershed grid equivalent to running r.water.outlet for multiple outlets r.drain Traces the least-cost (steepest-downslope) flow path from a given cell. Stops in pits. Input: elevation, point coordinates Output: least-cost path r.water.outlet Generates a watershed basin from a flow direction map. Ehlschlaeger, USACERL. Input: flow direction (from r.watershed), basin coordinates Output: watershed basin map GRASS Raster Flow Functions:  GRASS Raster Flow Functions r.basin.fill Generates a raster map of watershed subbasins. Larry Band. Input: stream network (from r.watershed), thinned ridge network (by hand!) Output: watersheds subbasins r.topmodel, r.topidx Simulates TOPMODEL, Keith Beven. Input: elevation, basin, TOPMODEL parameters file Output: flow direction, filled elevation, tci, watersheds, [..] r.flow, r.flowmd Constructs flowlines, flowpath lengths and flowline densities. Flowlines stop in pits. Mitas, Mitasova, Hofierka, Zlocha. Input: elevation, [..] Output: flowline density, flowlines (vector), lengths More complex models r.water.fea - Finite element analysis program for hydrologic simulations r.hydro.CASC2D - Fully integrated distributed cascaded 2D hydrologic modeling. r.wrat - Water Resource Assessment Tool Preliminary Experimental Results:  Preliminary Experimental Results PIII dual 1GHz processor, 1GB RAM Panama DEM:  Panama DEM Panama r.terraflow MFD:  Panama r.terraflow MFD r.terraflow MFD zoom,3D:  r.terraflow MFD zoom,3D r.terraflow SFD zoom,3D:  r.terraflow SFD zoom,3D r.terraflow MFD zoom,2D:  r.terraflow MFD zoom,2D r.terraflow SFD zoom,2D:  r.terraflow SFD zoom,2D r.terraflow MFD TCI zoom,2D:  r.terraflow MFD TCI zoom,2D r.terraflow SFD TCI zoom,2D:  r.terraflow SFD TCI zoom,2D Flat DEM:  Flat DEM r.terraflow MFD:  r.terraflow MFD r.terraflow SFD:  r.terraflow SFD r.watershed:  r.watershed Conclusions/Future Work:  Conclusions/Future Work Work in progress More features Water outlet queries Watershed delineation Experimental analysis Other features? Modeling? Other (intensive computing, I/O-bound) applications?*/terraflow*/terraflow*/terraflow

Add a comment

Related presentations

Related pages

GRASS Bewegungs-Systeme

Hier können Sie die gesam­melten GRASS Produkt­kataloge online Durchblättern. Die Kataloge sind immer auf dem neusten Stand und bieten Ihnen eine ...
Read more

Günter Grass – Wikipedia

Günter Grass war offizieller Unterstützer der Aktion 1:1. des LSVD, die sich für gleiche Rechte und Pflichten bei einer Lebenspartnerschaft einsetzt.
Read more


GRASS GIS is a free Geographic Information System (GIS) software used for geospatial data management and analysis, image processing, graphics/maps ...
Read more

Gras – Wikipedia

„Gras“ als Metapher. Einige Redensarten benutzen das „Gras“ als Metapher: Dem Gras beim Wachsen zusehen für z. B. „Langeweile“ Gras rauchen ...
Read more

Grass Infos -

Die Seiten bietet Ihnen Informationen und weiterführende Links zum Thema Grass. Grass Informationen erhalten Sie online im Internet ...
Read more | grass | Wörterbuch Englisch-Deutsch

Übersetzung für grass im Englisch-Deutsch-Wörterbuch
Read more

Günter Grass – Schriftsteller, Nobelpreisträger ...

Günter Grass ist einer der bedeutendsten deutschen Schriftsteller. Doch spätestens seit er den Literaturnobelpreis erhalten hat, ist er nicht mehr nur ...
Read more


Stimmen zum Tod von Günter Grass: "Er wird neben Goethe stehen" SPIEGEL ONLINE - 13.04.2015 . Von Salman Rushdie bis Angela Merkel ...
Read more

Gras – Wiktionary

... Grass. Worttrennung: Gras, Plural: Grä·ser. Aussprache: IPA: [ɡʀaːs] Hörbeispiele: ...
Read more

Poaceae - Wikipedia

Prior to 2005, fossil findings indicated that grasses evolved around 55 million years ago. Recent findings of grass-like phytoliths in Cretaceous dinosaur ...
Read more