ࡱ> xzwG Jbjbjَ tF] ll vv~  K  3 $"JW W v~ ~ :~ B4`|fgĺt Urban Growth Model (UGM) Version 3.0 Differences between Version 2.0 and 2.1 Version 3.0 is a complete rewrite of version 2.0. Version 2.1 was released while 3.0 was still in development. However, all improvements in 2.1 have since been rolled into 3.0. What follows is a breakdown of some of the changes by category. Memory Prior to 3.0 the UGM had a very inefficient memory model. To allocate space for a single MxN image required M+1 malloc calls. So if your data set consisted of 36 1000X1000 images the UGM would make 36,036 malloc calls just for the input images. There were also malloc and calloc calls scattered throughout the code for allocating work space. Malloc calls are time consuming, but the real problem is that you have no control over how the memory is laid out. For example you can never be sure that two consecutive rows of a given image are consecutive in memory. Most architectures benefit from consecutive memory accesses. In fact on the Crays you cannot use a lot of the optimization techniques if your memory is not contiguous. Version 3.0 has its own memory manager. At start up the code determines the required memory from the number and sizes of the input images. It then allocates one large piece of memory which it then partitions into the needed chunks. There are only 3 locations in the code which contain malloc calls. One is for the large memory chunk described above. It can be found in the memory_mgt.c module. The second is in output.c and is used to malloc space for color maps. The third is in main.c and is used only when the code is compiled with the MEMORY_CHECK macro defined. This switch causes the code to check the integrity of the input images just before the code exits. If the input images have been modified during the execution of the model then there is a memory problem. It is probably a good idea to always compile with this flag. A typical run might require: 4 or more urban seed images 2 or more transportation network images 0 or 2 landuse image(s) 1 slope image 1 exclusionary image 1 background image 10 or so landuse classification workspace images 13 general workspace images  36 images for this typical scenario If the images are 900 X 900 pixels, then space is needed for 36 x 900 x 900 = 29,160,000 pixels. To get the number of bytes needed multiply by the macro BYTES_PER_PIXEL. This macro is defined in globals.h as follows: #define PIXEL long #define BYTES_PER_PIXEL sizeof(PIXEL) Note how BYTES_PER_PIXEL works off of PIXEL. For the current platform you would choose the type for PIXEL. On the Cray a long, int, and short are all 64 bits. long is chosen for the Cray to remind the programmer of this fact! So on the Cray we have (29,160,000 * 8)/1048576 = 223MB. This might just fit on a single node of the Cray T3E whichhas 256MB per node. It will not fit on the Cray T3D which has 64MB per node. Also, there is a minor complication which will add to this memory requirement slightly. Since each image must start on a word boundary, each image size is rounded to the word boundary, and then this rounded value is multiplied by the total number of images. To see how this is done refer to the code in module memory_mgt.c. Since memory is a limiting resource in the UGM and the Cray wastes 7 of 8 bytes in Cray word hold in a 8 bit pixel, the user is provided with the option of data packing all but the 13 general work space images. To turn on packing the code should be compiled with PACKING defined. Packing can reduce the memory requirements of the above typical scenario to 99MB. The packed images remain packed until they are needed for processing. When the data is needed the image is unpacked processed and repacked. Structures The structures in 3.0 have been completely rewritten. Prior to 3.0 most structure information was contained in the Params structure which as declared as pvals. pvals was then passed around to just about every function. A function having access to pvals had access to just about everything. All the variables might just as well been declared global. There were several things in Params which should not have been there. For example the constant pi, and the Booleans true and false. Also, prior to 3.0 all structure information was contained in the info.h header. In 3.0 all the structures have been broken out into several new headers, one for each module. So the structures unique to a module are in the respective module.h file. The ugm_typedefs.h header contains structures which most if not all modules need to see. All global variables are in globals.h are prefaced with glb_ to identify it as global. Modularity The version 3.0 is a modular design with following modules: MODULE HEADER deltatron.c deltatron.h driver.c driver.h growth.c growth.h init.c init.h input.c input.h main.c memory_mgt.c memory_mgt.h output.c output.h random.c random.h spread.c spread.h stats.c stats.h utilities.c utilities.h ugm_typedefs.h deltatron.c contains all the code and only the code related to processing of deltatrons. driver.c contains all and only the code needed to drive the simulation. growth.c contains the code for the Monte Carlo simulation. init.c contains some on the initialization code. main.c contains some initialization code and the fifth order parameter loop. memory_mgt.c contains the memory manager code. output.c contains all the output routines. random.c contains the random number generator code spread.c contains the code which performs urban spreading. utilities.c contains utility functions used by other modules. All functions which are local to a module are declared as static. This prevents other modules from calling these local functions. Excluding global variables all variables used by a function must be passed in on the stack. This has three benefits. First, just by looking at the function interface the programmer can tell what the function needs and what it returns. Second, it doesn't give the function access to structures it shouldn't have. Third, it makes the code more readable. Compare these lines: From 3.0. sprintf (filename, "%scumulate.landuse.gif", glb_output_dir); date_str = input_gif>urban[input_gif>urban_count  1].year.string; out_write_gif (cum_probability_ptr, out_annual_colortable_p, filename, date_str, 8); From 2.0 WriteGrid2 (pvals, grid, "cumulate.urban.gif", 0, 11); In the 3.0 version we are writing the data at location cum_probability_ptr to the cumulate.landuse.gif file using the out_annual_colortable_p color map and adding a date with index color 8. In the 2.0 version we can see that we are writing to the cumulate.urban.gif; however, if we want of know the location of the data, the color map or the date information we must track down the WriteGrid2() function and analyze the code to determine what is happening. Logic In spread.c, phase1, phase2, and phase3 growth has been combined into a single function, spr_phase1n3, which represents phase1 and phase3 growth types. Phase1 being diffusion and phase2 being breed growth. Deltatron has been completely rewritten. I cannot describe the differences between deltatron 3.0 and previous versions, since the previous version was unintelligible. Please refer to the code for a description of the current processing. Road data is now weighted relative to the highest road value. Larger roads should produce more urban sprawl. Within the road gravity box the road search is now done in an outward search pattern. Massively Parallel Processing Massively Parallel Processing (MPP) is achieved using the Message Passing Interface (MPI). Only the calibration phase of the model has been parallelized. Excluding the naming of some output files, all the parallelization takes place in the main routine. The main function contains a fifth order loop over the diffusion, breed, spread, slope and road gravity coefficients. Each time through this fifth order loop the driver() function is called. The driver starts an independent execution of the Monte Carlo simulation each starting with the same random seed. The parallelization is done by giving each processor its own version of the driver processing to work on. Each processor is allowed to run independently of the others (i.e. no need to communicate status or synchronize). The MPI code in main is : MPI_Init (&argc, &argv); MPI_Comm_rank (MPI_COMM_WORLD, &glb_mype); MPI_Comm_size (MPI_COMM_WORLD, &glb_npes); : : if (glb_current_run % glb_npes == glb_mype) { : : } : MPI_Finalize (); : exit(0); glb_npes contains the total number of processors the UGM is running on. glb_mype contains the rank of the processor in glb_npes. glb_current_run is the current run through the fifth order parameter loop. The line if (glb_current_run % glb_npes == glb_mype) doles out the tasks to the processors in a round robin fashion. Since the calls to driver() should all be about the same size in execution time and our target architecture is homogeneous (all processors the speed), then this round robin algorithm balances well. Since the processors are allowed to race along with out synchronizing with each other, the output files had to be suffixed with glb_mype to prevent two processors from writing to the same file at the same time. After the job is finished the individual files must be merged together. User Interface The three files landuse.dates, roads.dates, and urban.dates have been combined into a more user friendly file, input_images.list file. An example of this file follows: # List of input images for UGM version 3.0 # # Comments start with # # INPUT_DIR=/work/tsb/NESC_UGM/UGM/input/demo50/ OUTPUT_DIR=/work/tsb/NESC_UGM/UGM/output/ # < > = user selected fields # [< >] = optional fields # # Urban seed data GIFs # format: .urban..[].gif # # demo50.urban.1930.gif demo50.urban.1950.gif demo50.urban.1970.gif demo50.urban.1990.gif # # Road data GIFs # format: .roads..[].gif # demo50.roads.1930.gif demo50.roads.1950.gif demo50.roads.1970.gif demo50.roads.1990.gif # # Landuse data GIFs # format: .landuse..[].gif # demo50.landuse.1930.gif demo50.landuse.1990.gif # # Excluded data GIF # format: .excluded.[].gif # demo50.excluded.gif # # Slope data GIF # format: .slope.[].gif # demo50.slope.gif # # Background data GIF # format: .hillshade.gif # demo50.hillshade.gif Blank lines and lines beginning with # are ignored. This approach allows user to put all the names of his input files in one single file. Doing this would have the following benefits: 1. The UGM code would be simpler because it would only have to process one file instead of three. 2. The user would only have to maintain one file instead of three. 3. The user could add comments to the input file list 4. The user could view the complete list of input GIFs in one file. 5. The user could easily comment out an image file he didn't want to process. 6. The name of the background file would be user selectable. In earlier versions it was hard coded.. 7. You can add format or other instructions for the user in comment sections. 8. By reading in these file names into arrays the UGM would not have to reconstruct the input file names before reading the GIF files. This means cleaner code and less chance of making an error. 9. The UGM will still have to parse the strings for location and date information in order to construct output files. This is OK. There is no chance for the user to miss type the location if we don't ask him for it. 11.T he INPUT_DIR and OUTPUT_DIR fields allow the user to direct the UGM to where the input data is located and where the output should be written. The user will no longer have to copy input data in and out of the Data directory. This improvement will reduce the chance of user error. If either of the INPUT_DIR or OUTPUT_DIR fields are commented out, then its value will default to the current directory. A suggested directory setup would be: scripts ------ | | input output | | ------------- ------------- | | | | | | demo50 demo100 demo200 demo50 demo100 demo200 Scripts would contain scripts for executing the UGM and input_images.list files pointing to the proper I/O directories. SCCS ID All C modules and header files now have SCCS ID's for tracking version numbers. For example in driver.c the id looks like: char driver_c_sccs_id[] = "%W% %G%"; When it is expanded it will look like char driver_c_sccs_id[] = "@(#)driver.c 3.0 3/2/00"; By looking at the expanded SCCS ID the programmer can tell what version of the module he has. Also using the SCCS utility he can recall previous versions from the SCCS directory. Once the code is compiled into a binary the what command can be used on the binary to identify what versions of the code was used to compile the binary. Below is an example of the what command. (308)% what grow grow: driver.c 3.0 3/2/00 deltatron.c 3.0 3/2/00 input.h 3.0 3/2/00 input.c 3.0 3/2/00 growth.h 3.0 3/2/00 growth.c 3.0 3/2/00 stats.h 3.0 3/2/00 stats.c 3.0 3/2/00 output.h 3.0 3/2/00 output.c 3.0 3/2/00 utilities.h 3.0 3/2/00 utilities.c 3.0 3/2/00 spread.c 3.0 3/2/00 init.h 3.0 3/2/00 init.c 3.0 3/2/00 random.h 3.0 3/2/00 random.c 3.0 3/2/00 memory_mgt.c 3.0 3/2/00 globals.h 3.0 3/2/00 ugm_typedefs.h 3.0 3/2/00 main.c 3.0 3/2/00 Asserts There are many asserts in the code to catch errors early. Every function asserts the correctness of its input. This makes catching bugs a lot easier. During the development and testing of the UGM the asserts should be turned on. The programmer does not have to turn the asserts on; they are on automatically. Instead he must turn them off. This is done by compiling with the NDEBUG switch. When turned off the asserts are mapped into blank lines by the C processor. For optimal speed compile with NDEBUG. If the code is not working correctly the first step in debugging should be to turn asserts on. Validation of Inputs Where ever possible the input data is validated against acceptable limits. Earlier versions of the UGM did almost no validation of input. Here are few of the examples of validation: 1. All of the GIF input files must have the same location name. 2. All of the input GIFs must have the same number of rows and columns. 3. All the input GIF files must exist. 4. All the input GIFs must be of format GIF87a. 5. input_image_list_file must exist. 6. In order to simplify certain data structures it was necessary to an upper limit on the number of road and urban images which the UGM can input. These values are set in globals.h as: #define MAX_URBAN_YEARS 15 #define MAX_ROAD_YEARS 15 If the user exceeds this number he will get a warning message instructing him to increase the values of MAX_URBAN_YEARS and/or MAX_ROAD_YEARS and recompile. 7. The number of landuse classes are checked against MAX_NUM_CLASSES in similar way as in #6. 8. Filename cannot exceed MAX_FILENAME_LEN set to 150 chars. If the user exceeds this number he get an error message stating the problem. Tracing There are 3 macros for tracing the execution in the UGM code,CALL_TRACE, RETURN_TRACE, and TRACE. The first executable statement of each function is CALL_TRACE, and the last executable statement of each function is RETURN_TRACE. CALL_TRACE and RETURN_TRACE are turned on at compile with the CALL_TRACING and RETURN_TRACING switches. If the model is crashing at an unknown location, turn on one or both of these traces to find the function causing the crash. TRACE is a macro which the programmer can sprinkle through out the code to trace individual line numbers. Just place TRACE on the line you wish to trace. Miscellaneous 1. Fixed memory leak when echo was off 2. 2.1 didn't check return code of malloc or calloc The first line of each function starts with an identifier: char func[] = "spr_urbanize_nghbr"; This string is used in output calls to tell the user which function is currently executing. Did not use any unbracketed if or for loops. Makes code easier to read and less likely to make errors when modifying code. Removed lots of dead code which didn't do anything but burn up CPU cycles. In lots of places inefficient code was cleaned up. For example: The many line function Float_to_String() was replaced with sprintf(). The 20 or so lines for merging background images was replaced with as little as 3 lines of code. When processing clusters the link list has been replaced with a circular queue. All globals are in globals.h Fundamental structures to the model are in ugm_typedefs.h Cumulate is always TRUE; therefore, test for cumulate have been removed Changed many variable names to more meaningful names Fixed bias in neighbor selection process. Now each neighbor has an equal probability of being selected. PAGE 2 ODJ&x}""))77<<*?>?CCF FuJvJ{J|J}J~JJmHnH jU55CJ'OPQCDKL\  g h   I e i $'OPQCDKL\  g h   I e i ? i j } Vvjk'(d{"<Vp h!P{'(!"-.r4Sluwx~ di ? i j } Vvjk'(d{ p `"<Vp h!P{'(! p `!"-.r4Sluwx~M N ;!>)?*???@???9@:@@@@@@@AAAAAAAABB¿|yv {|GHABWX-Rx6\ -::::%;K;q;;;; </<T<z<<<<<<=>>)?*???@??? p `?9@:@@@@@@@AAAAAAAABBBBBCCCC$EdE H 0 `BBBBCCCC$EdEeEEFFF8F9FoFpFFF/G0GGGGGHH1I3IPIQIRIIIII|xpmeb                 A  HIrs]%dEeEEFFF8F9FoFpFFF/G0GGGGGHH1I3IPIQIRII ` ` ` 0 `IIII J JtJuJJJJJJ $& #$$d ` I J JtJuJJJJ     '0P/ =!"#$%* 00P/ =!"#$%* 00P/ =!"#$%* 00P/ =!"#$%* 00P/ =!"#$%* 00P/ =!"#$%* 00P/ =!"#$%* 00P/ =!"#$%* 00P/ =!"#$%* 00P/ =!"#$% [4@4Normal1$CJhmH nH <A@<Default Paragraph Font4&@4Footnote Reference<O<Level 1 & F0@& hx"*).6=REF)Uٺ1] JIi !C%*-,0P6:?dEIJJLMNPQRSUWXZ[|0:BIJKOTVY\ !tJeannette Candau4C:\WINDOWS\Profiles\nette\Desktop\UGMDifferences.wpd 0CJOJQJ.0.TsTSss0 .s1s2Us3Us4Vs5DVs6xVs7Ss0.Ss1t28t3lt4t5t6t7@HP OfficeJet T Series PrinterLPT1:HPODJC05HP OfficeJet T Series PrinterHP OfficeJet T Series Printer; d,,HP OfficeJet T Series PrinterLPT1 ,,dHP OfficeJet T Series Printer; d,,HP OfficeJet T Series PrinterLPT1 ,,d@sF@@G:Times New Roman5Symbol3& :Arial" h2 T9 T ;7  ;7 # DDtFJeannette Candau Oh+'0\   $ 0<DLTssss Normal.dotJeannette Candaud2anMicrosoft Word 8.0@V@qhú@bĺ  ;7 ՜.+,D՜.+,, hp|  D   Title 6> _PID_GUIDAN{CBCE6900-267C-11D5-830E-444553540000}  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]_`abcdefhijklmnpqrstuvyRoot Entry Fcúngĺ{1Table^`WordDocumentSummaryInformation(gDocumentSummaryInformation8oCompObjj  FMicrosoft Word Document MSWordDocWord.Document.89q