Dear DDJ,
I am writing in reference to Michael Swaine's column "Programming Paradigms," in the April 1989 issue of Dr. Dobb's Journal. I have always enjoyed reading Swaine's columns and I am pleased to be writing to him.
I wanted to comment on his discussion of superlinearity. I share his skepticism about the results of Rao and Kumar about superlinear speedups with parallel processing. I feel that their example (in fact any example) of superlinearity falls into Swaine's first case, that is, of a better algorithm being used in the parallel case.
Nine processors, each running a depth-first search on a part of the search tree, are not together doing a depth-first search. They are running a similar (but different) algorithm that samples each part of the tree for solutions.
Suppose we wanted to run exactly the same algorithm on a sequential processor. First we implement a simple light-weight process (or thread) system with nine threads. Each thread simulates one of the nine processors running in parallel in the parallel solution. This method will exactly track the parallel algorithm at one-ninth the speed (plus a small constant factor for the multiprogramming). The constant factor for the thread switching only requires handling the timer interrupt and swapping register.
The exact value of the thread-switching overhead is not important anyway because we know it will be a constant factor and we can make it arbitrarily small by increasing the time slice value and considering larger trees. This method will approach exact linearity in the limit and it is only the large problems that one would benefit from using parallelism any way.
There are other ways to look at the same idea. We could dispense with actual multiprogramming and instead just sequentialize the parallel algorithm. That is, have the algorithm keep nine stacks and service them in rotation.
The reason that their solution seems to produce superlinearity is (as Swaine mentioned) that there are several solutions and the depth-first search method always goes left to right and will lose out to the parallel algorithm if the solutions tend to cluster elsewhere. Another solution would be to modify the depth-first algorithm to randomly decide to explore either the left or right subtree first and stack the other subtree. This method would visit a random leaf node first and then spread out on both sides of that node (randomly spreading left or right at each step) until it reached both sides of the tree.
If it turned out that it would be better to visit leaf nodes randomly (and not spread out from a randomly selected left node) you could pick randomly from the stack rather than always taking the most recent inserted element (which would make it a list, I guess).
As long as I am writing, I thought I might comment on Swaine's ideas for a first course in computer science. I am interested in this because I am an associate professor in the computer science department at the University of New Mexico (although I am currently on paternity leave).
First, I might mention that we just added a course called "Programming Paradigms" although at the senior level. The thing I liked best about Swaine's proposal is the emphasis on reading programs rather than writing them. If the analogies to reading and writing natural language or learning Morse code hold, then it would be much easier to learn to read a program than to learn to write one. As a result you could cover much more interesting and complex programs in the first course. In addition, learning program reading would help later in doing program maintenance, which we know is a major activity of working programmers.
A related proposal I have been hearing for a while is that the first course in computer science should (like the first course in other sciences) survey all the important parts of the field rather than just teach programming. I would tend to merge Swaine's proposal into that one since computer science is much more than programming and even the more general area of programming paradigms is just a part of the whole of computer science.
I do not see changes coming soon, however. I have been trying for several years to get our department to teach Scheme in the first programming class. (Scheme, rather than Lisp, so we can use Abelson and Sussman's book.) Then the students could be writing interesting programs (like Eliza or symbolic differentiation) rather than worrying about the problems of non-conditional ANDs in Pascal.
Let me close by saying again how much I enjoy Michael Swaine's columns. Keep them coming.
Charles Crowley
Albuquerque, New Mexico
Dear DDJ,
Contrary to what editors of PC rags think, reading skill in many languages and (I groan at the use of this too hip word) paradigms is not the most important skill that one can and should learn from one's first CS course. True, reading is a useful skill and one should learn it but it is hardly the most important thing to learn about computers and computer languages. I think that if you have to rank the items that you would most like your students to walk away with from a programming class they would be:
You can get all of this by teaching any computer language, however, the emphasis is on writing, not on reading. When reading you can skip over details, when writing you can't. Reading is lazy in comparison to writing.
By the way, are high-level languages like Fortran a different paradigm from assembly code? Is Quicksort a different sorting paradigm from, say, bubble sort? Is OOP with multiple inheritance a different paradigm from the traditional single inheritance OOP? Were big tail fins on cars the new paradigm in car design or just style? Is the word paradigm coming to mean anything that is a little different from something else but you want to emphasize how hard it was for you to learn the new thing by claiming that the new thing is revolutionary or radical? This hardly matches Khuns' [sic] use (yes, I know he used the word in 187 different ways in the 203 uses in his book) where he refers to one common mindset (Newtonian mechanics) that had to be replaced in light of new knowledge (relativity). Note the words "common" and "replaced." OOP is not replacing assembler and neither is parallel computing replacing sequential computing. They have all been around for years and are different fields of endeavor, they are not alternate views of one reality. The way Swaine uses the word paradigm is cute, adds zest to his articles (which I enjoy quite a bit, don't misunderstand me), and sparks controversy because it is fundamentally wrong, but somewhat defensible due to the vagueness of the word to begin with. It's a good way to spark reader feedback but is on the same level as using cheesecake photos to spark sales.
If I may render the opinion of an old computer hack, message passing, event-driven windows systems are new and an exciting territory to someone from the Hi-Level App school but is just business as usual to us ASM systems hacks who have been writing interrupt driven (message from the data unit #4 just came in at a higher priority than the disk, right when we were in the middle of ...) device handlers since the early 50s. We just wanted to share the joy of systems hacking to all the Apps writers. Yes, it is graphical and sexy and new and different from what you are used to, but revolutionary? Was structured programming and indenting revolutionary? Yes, people wrote spaghetti code with gotos but others of us felt is was unreadable and developed styles to limit the code flow so we could understand what was going on. When those became standardized and were given names in high-level languages was that the revolution? And now OOPs are the great new snake oil of the 90s. Boy, when you get objects you will really be set free! No more hard code to write. You want to print a floating point number you just tell it DISPLAY YOURSELF and it knows what to do. The fact that Basic has kept track of strings and integers and floats and printed them appropriately for years is not germain. The fact that for years people have kept fields in records to identify what type of record it is so that they can CASE to the right code is beside the issue. In OOPs it is all automatic. All your CASES are hidden from view, the code writes itself! Well, actually you do have to write all the separate cases, but instead of keeping them in one file of subroutines you can keep them in separate little files with the object classes! And you can inherit from one class to another, that was when it is appropriate to reuse it without even rewriting it! Radical! Of course, if the record is really different you have to write something new, but hey, you can use any of the other subroutines that you've already written to make it really easy!
Of course, if there are bugs you still have to go find them.
Fortunately, since you are reusing all these wonderful already debugged methods, the problem is always in the code you've just written, unless, of course, you made a mistake in one of the old methods that you just never exercised until just now. Also, if you design it wrong from the start, you may not know it until you finish because you start at the bottom with simple classes and build your way up (as opposed to top down) and you may have to rebuild the whole thing anyway, but we'll fix that in our next paradigm shift, eh? In short, my impression of the great progress in computer software in the last decade is that we have discovered some important things:
Marlin Eller
Seattle, Wash.
Dear DDJ,
The basis of the algorithm is a simulation of the hardware tapped shift-register used to generate CRCs. I show the registers shifting right while your implementation shifts left. Your feedback constant 0x1021 is the CCITT value 0x8408 bit-reversed. Your version of the implementation stores the data byte into the lower 8 bits of the left-shifted CRC in order to affect the data input which I show as a single bit input to the accum_crc function. My CRC is 16-bits, while your implementation requires a 24-bit CRC variable, of which the high-order 16-bits match my CRC variable.
I hope that this helps to clarify the CRC algorithm Al showed in his article. Considering the amount of interest I found when I published, you will probably get a number of letters from readers concerning the CRC function. There are much faster CRC algorithms which use small, precomputed tables to do the CRC calculation for an entire data byte at a time, eliminating the for loop required in the bit-by-bit algorithms I have devised.
Meanwhile, keep the articles coming! You do the readership a great service by publishing source code listings in the magazine. I've been a reader (and occasional contributor) for over 12 years now.
Robert D. Grappel
Concord, Mass.
Dear DDJ,
I am writing in response to a letter from Bruce Koivu that appeared in your April issue. Bruce was concerned with converting Rob Moore's "Mapping MS-DOS Memory Allocation" (November, 1988) program from Turbo C to Microsoft C. I have a few suggestions that may help Bruce in this process.
#pragma pack(1) struct MCB { char chain; unsigned pid; unsigned
psize; char fill[11]; }; typedef struct MCB huge *PTRMCB; #pragma pack( )The first pack pragma tells the compiler to perform byte alignment on any following structures. The second pack pragma tells the compiler to default back to word alignment.
/* far pointer to segment address/ /of first MCB * unsigned far *segmptr;/ /* get pointer to segment address of first MCB */ segmptr = MK_FP(sregs.es, regs.x.bx-2); /* get and return pointer to first MCB */ return MK_FP(*segmptr, 0);
in Microsoft C:
/* far pointer to segment address of first MCB */ unsigned far * segmptr; /* get pointer to segment address of first MCB */ FP_SEG(segmptr) = sregs.es; FP_OFF(segmptr) = regs.x.bx-2; /* get pointer to first MCB */ FP_SEG(segmptr) = *segmptr; FP_OFF(segmptr) = 0; /* return pointer */ return (segmptr);
This may seem strange at first (using a macro on the left side on an assignment statement), but a look at the macros themselves reveals that this is perfectly legal. Recall that a far pointer is stored in memory as an offset followed by a segment. Both may be treated as unsigned (16-bits). Through a series of casts to an unsigned pointer, these two macros access the segment and offset portions of a far pointer.
/* huge pointer to an MCB */ PTRMCB ptrmcb; /* get pointer to next MCB */ ptrmcb += ptrmcb->psize + 1;
in Microsoft C:
/* "huge"pointer to an MCB */ /* but, for some unknown reason at least to me) */ /* it is treated as far! */ PTRMCB ptrmcb; /* temporary to hold segment address of MCB pointer */ unsigned mcbseg; /* get pointer to next MCB */ mcbseg = FP_SEG(mcbptr) + mcbptr->size + 1; FP_SEG(mcbptr) = mcbseg;
Remember, both huge and far pointers may access any location in memory. However, when performing pointer arithmetic, such as the addition above, a far pointer only uses 16-bit math while a huge pointer uses 32-bit math! Since far and huge pointers are stored as offset followed by segment, one can see that the segment of a far pointer cannot be changed via simple addition! Of course, you may modify the segment directly as shown above.
Steve Smith
Renton, Wash.
Dear DDJ,
Our experience is that the joint venture in India significantly strengthens our global competitiveness. TUL has implemented scores of newly designed, leading-edge applications, and not just conversions as Mr. Little seems to imply. Increasingly, new software development projects are being undertaken within India, thanks to improving communications and satellite links. This, in my view, proves once again that clients will ultimately care more about quality, timeliness, and cost, than where a project is performed.
Anil Shrikhande
Unisys Corporation
Blue Bell, Penn.
Copyright © 1989, Dr. Dobb's Journal