Last entry I waxed poetic about how long my days are and how uneventful. That has changed slightly; now I spend a lot of time reading the eight tons of material I'm supposed to know. The ironic thing is, it really isn't that much reading - a couple of papers here, a few chapters there - its the thickness of the stuff that gets me. When a homework problem takes the better part of two hours just to "flesh out" - and I'm not even talking actually finish - things tend to bog down quickly. A quick example of this - on the last homework assignment, there were five questions. This one was the shortest - of which it was only worth one-ninth of the total points for the assignment. Read, and have a Kleenex ready for when blood inevitably shoots out your nose.
Problem: Design a constant time algorithm to perform modulo-m addition on a (m+1) x N R-Mesh.
Algorithm:
Model - (m+1) x N R-Mesh
Input - For 0 <= j < (N/2), processor(0, 2j) holds bit bj and bit b(N/2+j).
Output - For 0 <=i <= N, processor(i, N-1) sets a flag if and only if i is the modulo-m addition of b0 + b1 + ... + b(N-1).
begin
/* There are two input sets for the algorithm. The first are bits b0, b1, ..., b(N/2 - 1). The second set is the bits b(N/2), b(N/2 + 1), ..., b(N-1). These input sets are held in the even-columned processors, as determined by the input of the algorithm. Index k is used to refer to the kth bit in each input set. */
1. Processor(0, 2j), for 0 <=j <(N/2), broadcasts bk to all processors in column j and column j+1.
2. If bk = 1 then
if j is even then processor(i, j) configures {NE, SW}.
if j is odd then processor(i, j), for 0 < i < m, configures {NW, SE}.
3. If bk = 0 then processor(i, j) configures {N, S, EW}.
4. Processor(0,0) sends a signal on its West port and processor(i, N-1) reads from its East port.
5. Processor(i, N-1) sends a signal to processor(i, 0). Steps 1 through 4 are repeated for the second set of bits bk, with the processors reconfiguring their ports based on this second set of bits. In step 4, the signal is sent from processor(i, 0), instead of processor(0, 0). Processor(i, N-1) detects the signal in the second interation of Step 4, setting the flag to indicate the modulo-m addition of b0 + b1 + ... + b(N-1).
end
There was a lengthy part proving the correctness of the algorith that followed, but you get the idea. I write about five of these style algorithms every week or two, plus proofs proving the correctness of the algorithms. Thats for one class. Another class is extending some very lengthy and counter-intuitive proofs to input sizes and sets beyond their inital assumptions - not an easy task for me, since I suck at proofs about as much as any self-respecting Electrical Engineer getting his masters in parallel architectures can.
Its a joy.
All of this is why I don't update much however; after about 4 or 5 hours of this (a day, usually) its about all I can do not to just crawl into my bed and sleep so my brain doesn't explode out my ears. I find solace, however, in the likely places. Beer, video games, and T.V. keep me sane.
On another note: I'm looking forward to watching the pres debates tonight. Its not that I think George Bush ISNT going to look like a total deuchebag, or that Kerry ISNT going to look like a complete automata, its just that I enjoy seeing two powerful men make asses of themselves on T.V. for the general amusement of all.
Or at least myself.
Miss Any?
Alright, we're gonna give this a shot
January 02, 2005
Let's see how badly I failed these last year
December 31, 2004
Okay, so its trendy
December 28, 2004
Its just like that asshole, Joe fucking Lieberman. Annoying and rather pointless.
December 27, 2004
Is this a typical Christmas?
December 26, 2004