Photo CD Demo 1

home *** CD-ROM | disk | FTP | other *** search

/ Photo CD Demo 1 / Demo.bin / cellsim / v2_5 / doc / cm.fcn < prev next >

Wrap

Text File | 1990-02-26 | 17.2 KB | 386 lines

Documentation for Cellsim v2.5 Connection Machine Update-Functions February, 1990 **************************************** LOOKUP TABLE RULES ON THE CM To make lookup table (LT) rules for the CM, you just do what you do to make them for the Sun. The CM uses the exact same format for LTs as the Sun. See the "Rule_README" file for information on generating LTs. (The "Rule_README" also describes how to generate computed-function rules for the Sun, since it's almost identical to generating lookup-tables). **************************************** COMPUTED-FUNCTIONS ON THE CM ("Ah, Paris...") It would be nice to have some kind of program around that you could feed a normal C update-function, and it would turn it into Paris. Well, nobody's done that yet, that we know of. So if you want to use computed-function rules on the CM, you have to use C/Paris. C/Paris is just Paris when you call it from C. Paris, if you aren't familiar with it, is something a little above an assembly-level language (it stands for "PARallel Instruction Set"). You mostly deal with simple operations like "move", "add", "compare", "set context flag", although you don't have to worry about normal assembly-language stuff like how far you can jump, or which register an instruction has to use. If you don't have one already, you should get a copy of the Paris manual, which has a brief introduction to CM memory fields and context flags and the various instructions at the beginning, and which is mostly made up of a dictionary of Paris instructions. Your Thinking Machines representative should be able to help you get the documentation you need, or speak to the people who gave you your CM account. So, anyways, those of you who know Paris probably skipped most of that. Here are the details of what happens with computed-function rules on the CM. Cellsim (or rather cm_cell, the program running on the CMFE) keeps the current image in an 8-bit field called "cell"; just before calling your update function, Cellsim will look up the neighbors of the current neighborhood, and store them in a set of fields. Your update-function is then called. You can do whatever operations you like using these neighbor-fields, as long as your store the final result back in the 8-bit "cell" field. Those of you familiar with Paris realize that you often need some scratch space to do things, such as to keep intermediate results. Cellsim lets you allocate extra fields on the CM (as much as you need, as long as you don't run out of memory) to use within your update-function. So, let's go on and get more specific about all of this. **************************************** WRITING AN ACTUAL UPDATE-FUNCTION First, just as with writing Sun update-functions, you need the Makefile. The Makefile is in the "CM2/Rule_src" directory; you should make a copy of it in whatever directory you'll be keeping your Paris rules. Once you've made your copy, be sure the definition of "CM_MDIR" points to the full pathname of the "CM2/Rule_mdir" directory, which is where the include file and stuff are, that your rule needs. Ok, let's see how to make our Paris function. The first thing in your file, besides any comments, must be the line: #include "CMnborhood.h" which defines the fields containing neighbors, the "cell" field, some macros useful if you have to do NEWS operations, the global parameters parm1 and parm2, and the current value of the phase variable (if you're using the Margolus neighborhood). CMnborhood.h also includes the CM include-file <cm/paris.h>. Next, you need to declare two functions: your update function, and your exit function. The update-function is the routine which will compute the new values of the cells, and the exit-function is something you have to write to clean up, or deallocate any local CM fields your routine creates. Both should be declared to return a byte (which has been typedef'ed to be unsigned char). While in practice, you don't return anything from either function, future releases might want a return-value for some reason. So, for example, you might declare these function as follows: byte my_update_func(), my_exit_func(); Next, declare any static (private) variables you want, such as CM fields. For example, the heat.m256 rule has the following declaration: static CM_field_id_t heat_sum; where the heat_sum field will be used to add up the values of the neighbors. Then, after you've declared any local stuff you need, you should write your init_function. This must set the value of update_function to point to your update function declared above, as well as initialize any local variables or the global parameters if you like. This includes allocating space for your CM fields. So, for example, the init_function for the heat.m256 rule looks like this: void init_function() { update_function = heat; parm2 = 2; heat_sum = CM_allocate_heap_field(12); } We tell Cellsim that our update_function is "heat" (which we declared above, and which will be implemented below); we initialize the global parameter parm2 to a default value appropriate for this rule, and then we allocate 12 bits for our heat_sum field. You should allocate your private CM fields as heap fields. Next comes the update function itself. Here's what the update-function looks like for the heat.m256 rule: byte heat() { CM_u_move_2L(heat_sum, MNorth, 12, 8); CM_u_add_3_3L(heat_sum, heat_sum, MSouth, 12, 12, 8); CM_u_add_3_3L(heat_sum, heat_sum, MEast, 12, 12, 8); CM_u_add_3_3L(heat_sum, heat_sum, MWest, 12, 12, 8); CM_u_add_3_3L(heat_sum, heat_sum, MNW, 12, 12, 8); CM_u_add_3_3L(heat_sum, heat_sum, MSW, 12, 12, 8); CM_u_add_3_3L(heat_sum, heat_sum, MNE, 12, 12, 8); CM_u_add_3_3L(heat_sum, heat_sum, MSE, 12, 12, 8); CM_u_add_3_3L(heat_sum, heat_sum, MCenter, 12, 12, 8); CM_u_truncate_constant_3_1L(heat_sum, heat_sum, 9, 12); CM_u_add_constant_2_1L(heat_sum, parm2, 8); CM_u_move_1L(cell, heat_sum, 8); } (Things like "MSouth", "MNW", and so on will be explained later. They are the Moore neighbors). Basically, we add up the values of the Moore neighbors into the heat_sum field; we then divide it by 9 (using truncation integer division), and add in the value of parm2. Finally, we move the result into the "cell" field. Note that we don't need take the result modulo 256, because we are using 8-bit arithmetic, so the modulo-256 happens automatically. The last thing you need to write is your exit function. This is necessary to deallocate any fields your rule created, otherwise we'd run out of memory on the CM if we kept loading new rules. In the heat.m256 rule, this is all that's in the exit function: byte heat_exit() { CM_deallocate_heap_field(heat_sum); } We simply deallocate the heat_sum field, since that's all we allocated. If you allocated several fields in the init_function, you should deallocate them all. If you allocated any front-end variables, e.g with malloc(), you should use free() to free up the memory here as well. Now that we ran through an example without too many details, let's back up for some important info that we skipped over. **************************************** NEIGHBOR-FIELDS THAT ARE DEFINED FOR YOU In the heat.m256 rule, we used such CM fields as MSouth, and you may have been thinking "what is MSouth?" It is one of the standard Moore neighbors. You get the following neighors with the following neighborhoods: Moore: MCenter, MNorth, MSouth, MEast, MWest, MNW, MSW, MNE, MSE Von-N: VCenter, VNorth, VSouth, VEast, VWest Margolus: MargCenter, MargCcw, MargOpp, MargCw, MargPhase Linear radius1: LR1_L, LR1_C, LR1_R Linear radius2: LR2_LL, LR2_L, LR2_C, LR2_R, LR2_RR, Linear radius3: LR3_LLL, LR3_LL, LR3_L, LR3_C, LR3_R, LR3_RR, LR3_RRR (Note that in Margolus neighborhood, you get the phase variable both as a CM field, and as an integer on the front-end. Sometimes it is useful to have it in either of those places.) While the naming scheme may not be the best, if you really hate those names, you can #define new names in your update-function file, e.g. #define MooreNorthWest MNW if you like to be verbose. All of these neighbor fields are 8-bit fields. **************************************** AN UNFORTUNATE BUT IMPORTANT NOTE Due to some problems with dynamic-linking that we haven't worked out yet, there is one unfortunate step you might have to take when writing a Paris update-function. Namely, when your function gets linked in, if there are any paris calls you use that Cellsim doesn't use, they will not have been linked in to the cm_cell executable. Despite attempts at manually linking in the Paris libraries, this problem still persists. Therefore, if you use a Paris call that isn't already in Cellsim, you'll have to add it into Cellsim and recompile cm_cell. Here's how you do this: in the file "dummy.c", there is a single function called "dummy". It never gets called; however, it contains calls to very many Paris routines (extracted from the Paris library of one of the CMs I use). If you're using a Paris call in your update-function that isn't listed in dummy(), you should add a call to that Paris function in the dummy function, and recompile cm_cell by typing "make". We really hate having to do this, and are working on fixing it. If you find a way around it, please let us know. Once we get it fixed, we'll distribute a patch that you can apply to solve the problem. Hopefully, in the rules you write, you won't encounter this. However, if the CM software libraries get upgraded, that may cause problems with this scheme (requiring us to distribute a new dummy.c, if we haven't implemented a more elegant solution by then). **************************************** A SPECIAL NOTE ABOUT THE LINEAR NEIGHBORHOOD A special note must be made about the linear neighborhood. In order to let your rule know which VPs have a cell that is on the bottom row (the current row), there are 2 more CM fields defined. They are "bottom" and "not_bottom", and they are each 1-bit fields. In the linear neighborhood, when your update-function is called, the context-flag has automatically been loaded with "bottom", so only processors on the bottom row are active. However, if you do some fiddling with the context-flag in your rule, you should be careful to always AND the context-flag with the "bottom" field before altering the value of "cell". After your update-function returns, Cellsim will then activate the rest of the processors, to scroll the rest of the image up a row. You can deliberately violate these guidelines if you wish, and I did so once by accident with interesting results; but you should keep it in mind so you won't wonder why your 1-D rule is acting so strangely. **************************************** A LITTLE HELP IF YOU NEED TO DO NEWS OPERATIONS If you have some private CM fields in your rule, you may need to get them from neighbors using NEWS operations. Since I always get confused about which way is up when using NEWS ops, and since it's really up to the user which way is up, you need to know how I've defined things. Basically, you need to know which axis is horizontal and which is vertical, and then which direction is positive and negative along each access. To avoid having to always remember stuff like that, I just define macros to keep track of it for me. There are 4 macros: North, South, East, and West. Each macro holds the axis and sign (positive or negative, or upward and downward in CM terms) of the corresponding direction, in a form that can be used in a NEWS call. So, to get the value of "mycell" from your north neighbor and store it in "northval", you'd do the following NEWS call: get_from_news_1L(northval, mycell, North, 8) (assuming they are 8-bit fields). If you look at the "CMnborhood.h" file, you'll see that "North" is really defined to be "1, CM_downward", but there's no sense in remembering that. If you want to get the NEWS coordinate of each processor along a particular axis, I've defined the words VERTICAL and HORIZONTAL to be the respective axes. So you could do: CM_my_news_coordinate_1L(my_coord, VERTICAL, 9) to get your vertical coordinate and store it in the "my_coord" field. Note that coordinates are 9 bits, because the maximum image-size is 512. **************************************** A NOTE ABOUT WHEN YOUR INIT-FUNCTION AND EXIT-FUNCTION GET CALLED Your init-function and exit-function actually get called in circumstances other then when you just load your rule or when another rule gets loaded. Since Cellsim has the ability to change its image-size, when that happens on the CM, all fields are deallocated, and the current VP set is destroyed, so a new one with the new geometry (array-size) can be created. So whenever you change image-size on the CM, your exit-function will be called to deallocate the local CM fields in your rule, the new VP set will be created, and then your init-function will be called to create your local fields again on the new VP set. This shouldn't cause any problems, but it's just something you might like to be aware of. (If your init-function or exit-function print any diagnostic messages, you might have been surprised to see that happen whenever you changed image-size). **************************************** YOU CAN DO MORE THAN JUST 8 BITS ("Hey, a floating-point CA rule!") It turns out that you can really run more than 8-bit rules, provided you keep the data in one of your local fields, and as long as you have some way of getting data from Cellsim into your local fields. While I haven't done much with this yet, I did write a floating-point rule the other day. My init-function allocates a local 32-bit field to hold the floating-point value; the init-function also copies the "cell" field into my FP field, after re-scaling the values. So, the current image on the CM gets transferred into my FP field only when I load the rule; if I want to start with a different image, I send that new image to the CM, and re-load my rule. Then, after every time-step, I do a few extra Paris calls to re-scale the value in my FP field and store it in the "cell" field; so when my rule runs, you can actually get an image, although the image has far less precision per cell than the actual rule. While this may not thrill some of you (I'm not crazy about floating-point myself, I just wanted to see if it could be done), it should be very exciting to some of you. This means you can really run any type of 2-D Paris rule, and use Cellsim as a simple interface. For example, I have an 80-bit model of something like a cross between particles in a potential field, and simple flocking behavior. I originally wrote this as a stand-alone program using Paris, but now I can take the main update-function, and wrap it in Cellsim. While the Cellsim user-interface isn't very good for doing things this general yet, the potential is there to turn it into a very general and useful interface for using the CM, not just for cellular automata rules. So, if you have some ideas about all of this, we'd like to hear your comments. We already have some ideas for useful mechanisms to facilitate communication between the user and the update-rule, but more ideas would be appreciated. **************************************** SOME SAMPLE FILES Examples usually make things much simpler and easier to follow. So, some sample rules are included, in the "CM2/Rule_src" directory. Looking through them may clear up any confusion you have after reading this file. They are: heat.m256.c : simple heat rule heat.l256r2.c : heat rule in linear neighborhood heatb.l256r2.c : linear heat-rule where I accidentally added in the increment to *all* rows, instead of just the bottom row. bz.m256.c : Belousov-Zhabotinski style rule cycle.v256.c : Griffeath's "cyclic" CA rule cml.v256.c : the floating-point rule mentioned above Read the comments at the beginning of each file for more information on the rules. /* * * Cellsim copyright 1989, 1990 by Chris Langton and Dave Hiebeler * (cgl@lanl.gov, hiebeler@heretic.lanl.gov) * * This package may be freely distributed, as long as you don't: * - remove this notice * - try to make money by doing so * - prevent others from copying it freely * - distribute modified versions without clearly documenting your changes * and notifying us * * Please contact either of the authors listed above if you have questions * or feel an exception to any of the above restrictions is in order. * * If you make changes to the code, or have suggestions for changes, * let us know! If we use your suggestion, you will receive full credit * of course. */ /***** * Cellsim history: * * Cellsim was originally written on Apollo workstations by Chris Langton. * * Sun versions: * * - version 1.0 * by C. Ferenbaugh and C. Langton * released 09/02/88 * * - version 1.5 * by Dave Hiebeler and C. Langton May - June 1989 * released 07/03/89 * * - version 2.0 * by Dave Hiebeler and C. Langton July - August 1989 * never officially released (unofficially released 09/08/89) * * - version 2.5 * by Dave Hiebeler and C. Langton September '89 - February 1990 * released 02/26/90 *****/