Let's Make a CPU - Decision - The Stack

And so, after several days of thinking about it, I've decided how I want to do the stack and return address with my CPU. The theme of my CPU is bare bones simplicity while still being practical for use. As such, I've gone with the simplest possible solution.

At the time I thought that the link register method was the simplest solution, but this turned out to be incorrect. The link register method makes the stack a software structure, but leaves the link register up to the hardware (and the register can be accessed by software, no less). The simplest solution would be to leave both entirely up to software; the reason it wasn't obvious to me at the time was that there's no way to do this on x86-32, PPC, or MIPS.

All that's really needed for software to handle return addresses is a way to GET the return address. This can be accomplished by an instruction which loads an address relative to the current instruction pointer. Such an instruction would not be specific to return addresses, as it would be useful for other applications: it would make it possible to address data relative to code; neither x86-32, PPC, or MIPS can do this, and it would be of substantial benefit given how current operating systems work (x86-64 can, as I praised in my summary a month or two back).

How a PS3 Does It

IBM has released a variety of technical documents on the Cell (the Playstation 3's CPU, for those of you who are totally isolated from the world of video games). This seemed like a particularly timely piece of news, considering not only that I'm doing my own series on CPUs, but also that a few days ago I was looking around for information on how the Cell works, particularly with respect to how the synergistic processing units (SPUs) are programmed.

A bunch of the specs require registration. The only one that doesn't is this brief overview of the architecture.

I haven't had a chance to read any of this, yet (I just got back from school). Maybe, if I'm in a good mood, I'll look it over and write an architecture summary of the Cell, this weekend.

Let's Make a CPU - Dilemma - The Stack

As of right now, I have two major dilemmas in constructing the architecture. The first of these is what to do about the stack and function calls. I can think of 3 different ways to do it. But first, let me explain what I've already decided about the stack.

The x86 architecture (and possibly others that I don't know about) has the concept of pushing onto and popping off of the stack, using special instructions which cause the CPU to advance the stack pointer and store the contents of a register on the stack, in a single instruction. This is not how I'm going to do it. Like other RISC architectures, my CPU will treat the stack pointer the same as any other pointer: the program, prior to making a function call, will reserve stack space for the parameters by modifying the stack pointer, then store the parameters at the memory locations just reserved, and, once the call has returned, modify the stack pointer so as to remove the parameters from the stack.

Now, the three candidate stack models for me to choose between:

Integrated Stack
The first method is used by the x86 architecture. In it, a special (hardware defined) stack pointer register exists, which the program can modify as necessary (either by treating it as a pointer, or using the PUSH/POP instructions), and write to the stack. In addition to function parameters, the CPU uses the stack to hold the return addresses in function calls: the CALL instruction pushing the return address onto the stack, and the RET instruction popping it into the instruction pointer. The model here is a single, integrated stack, shared by both hardware (the CPU) and software (the program).

This method is elegant in it's simplicity: there is only a single mechanism to cover both bases. However, there are a few negatives to this method. On a philosophical level, this method completely dissolves the line between hardware and software; both the CPU and the program access the stack, mostly independently, but this still requires the software to know what the CPU is doing, and work around it. The practical side of this is that, as the software has full access to the stack, it's possible for the software to break the hardware (that is, by altering the stack pointer so as to cause an access violation when the CPU jumps to the return address), or to interfere with it (that is, the return address can be altered by the software, either intentionally - a function modifying the return address - or unintentionally - a buffer overflow exploit). Just the same, it's possible for the hardware to break the software (try forgetting about the 4/8 bytes the return address takes on the stack in an assembly program, and see how far your program gets before it blows up!).

Minimalistic Hardware
Several architectures, such as MIPS, do exactly the opposite. The stack is totally owned by the software, and the hardware has no knowledge of the stack. Function calls are handled by the call instruction copying the return address to a register; once this register receives the return address (inside the called function), this address becomes the property of the software (which must preserve this value, if the function makes function calls of its own), until ultimately the function returns by jumping to the return address in the register. The idea here is to have the hardware do the absolute minimum necessary, which amounts to copying the return address and jumping; everything else is done in software, including the jump to the return address.

This is elegant in its own way, in that almost everything is done by the software. The software, rather than hardware, takes responsibility for program flow, allowing (potentially) greater optimization of resource (particularly register and memory) usage. It has the added benefit of resisting (though not being immune to) code injection by buffer overflow, as only places where the return address is saved on the stack (as opposed to moving it to another register) are vulnerable. The downside is that it still allows functions to modify the return address; as well, there is still some mixing of software and hardware (although much less than with the integrated stack).

Software-Hardware Isolation
The final method is used, I believe, by Itanium. In this method, the CPU is again ignorant of the stack (at least, the stack used by the program), and uses a private, system stack (pointed to by a private register) for return addresses. (which may even be stored in on-chip cache, increasing the performance of returns considerably, as it allows the CPU to know ahead of time exactly where the function will be returning to, and prefetch the initial instructions).

This has the obvious advantage that it's immune to alterations (either intentional or unintentional) of the return addresses, as software does not have access to the system stack. The philosopher would also be pleased by the complete isolation of hardware (the call stack) and software. The downside is that it adds additional complexity to the CPU as well as the system, as now the system has two stacks (even though one is implemented in software, it still exists).

Let's Make a CPU - Basic Features

So, I can't wait to get started on designing this CPU, and this is the perfect kind of thing for me to put on my blog. So, first let's go over the basic features and why I chose them:

The architecture will be RISC. While a somewhat arbitrary decision, I think that RISC is much nicer than CISC, and particularly nice for an educational use such as this.

The CPU will use fixed-length instructions. While variable length instructions are easier and more spacious to decode, they're a major pain in a variety of circumstances.

The CPU will be 32-bit, and have instructions 32 bits large. While these are independent features, I decided that, for simplicity, the register size and instruction size would be the same. The reason I chose the size of 32 bits is due to what can fit in an instruction. 32 bits is the optimal size for instructions, based on several factors. 8 or 16-bit instructions are too small to fit all the parameters into, for many instructions. 64 bits, however, would be pretty wasteful, as most instructions won't use more than 16-24 bits.

There will be 32 (integer) registers. I don't really see a need for floating point registers at this time, and it would cause several complex problems I'd rather not get into. The number 32 was the very first thing to come to mind when I considered how many registers the CPU should have; however, when I started looking at how to pack the instructions, it turned out that 32 (5 bits worth) was the ideal number of registers, given the available number of bits in each instruction (if 32 had been too much to fit in an instruction, however, I would have had no choice but to reduce it).

The CPU will be little endian. Have plenty of friends that hate little endian with a passion, but it seems most reasonable to me. While about everything else is equal between little and big endians, little endian has the advantage of being able to downcast a variable without knowing exactly how large the variable is (i.e. can cast a 32-bit variable to an 8 or 16-bit variable without having to know anything other than that the variable is at least 16 bits).

The CPU will use two's complements integers. As I can't see any significant reason to use anything else (and plenty of reason to use this), this seems like and open and shut case.

& Work & Play

So, this week I started school. This is gonna be a really unpleasant semester, with three labs, and a few more units than I'm used to taking. However, there is some good news (and no, I didn't just switch to Geico): in the first computer archetecture class (today), they said that during the semester we (the students) will be creating our own CPUs on an emulator. I'm going to enjoy this immensely... *evil grin*

And as if school wasn't enough to occupy my time, I've found a game that I've been playing in my free time (which has only amounted to a few hours). Go on, guess. I bet you can't guess it.



Super Mario World. Yup, the first SNES game, back in 1991. For some reason I just had an urge to play it, so I'm playing it in all my free time (which really has only amounted to several hours). I'm currently at Chocolate Island.

Reader/Writer Lock - Introduction

Okay, enough procrastination; let's finish the thread synchronization object library. We've been over events, conditions, mutexes, semaphores, and atomic functions; that leaves us with only one left.

Suppose we have a linked list of something or other, which is accessed by multiple threads. Clearly it would be disastrous if two threads tried to add new entries to the end of the list at the same time. It would also be disastrous if one thread was iterating through the list (reading, only) while another thread modified the list in some way, such as inserting or deleting an element. Protecting the list with a mutex would handily solve the problem, as there would never be more than one thread accessing the list at once.

But consider what the consequence of two threads iterating (and reading from) the list simultaneously would be: nothing. So long as neither thread modifies the list, two threads can read from it without any problems, whatsoever. However, if the list is protected by a mutex, this is impossible, as only one thread can ever hold the mutex at a time; this is wasteful, particularly if the reads take a long time to execute.

The solution is the last kind of thread synchronization object: the reader/writer lock (also called a single writer, multiple reader guard). This type of lock can be locked two ways: for reading or for writing. When a thread has the lock for reading, other threads may enter the lock for reading simultaneously, but threads trying to enter the lock for writing must wait until all readers have left the lock. However, while a thread has the lock for writing, no more threads may enter the lock, regardless of whether they want read or write access.

A practical example of where this would be useful is in a database. Multiple threads may read from the database concurrently, but if a thread wants to write to the database, it must wait until it has exclusive access. Because reading from disk can be time-consuming, overlapping reads can significantly increase performance.

& Japanese

So this last week before the fall semester starts, I decided to improve my knowledge of Japanese writing, some. Specifically, I wanted to learn all of the hiragana and katakana (I already knew all but 6 of the hiragana), as well as 100 kanji (although that last part got torpedoed by a particular circumstance). If you have no idea what those three words mean, let me explain the basics of how Japanese writing works.

Japanese is composed of a very simple sound set: about 14 consonants and 5 vowels (note that English doesn't really have 21 consonants and 5 vowels, as many letters can be pronounced in different ways - i.e. there are about a million vowel sounds in English). Syllables in Japanese are a fixed unit of time that the syllable is spoken, regardless of which syllable it is. Syllables can be composed of a vowel alone, a consonant followed by a vowel, or a consonant alone; however, only a couple of consonant can exist without a succeeding vowel (n and s come to mind). Because of this very simple structure, it was decided that the phonetic alphabet would consist of one character per syllable. All in all this comes out to 71 characters; of these, 25 are duplicates of other characters, but carry some simple decoration to distinguish them.

There are actually two phonetic alphabets consisting of these same characters - the hiragana and katakana. Each has a character for each syllable, but the symbols for each alphabet differ. Hiragana is used to write (most) Japanese words. Katakana is used for borrowed words (that have been incorporated into Japanese - English is notorious for borrowing words) and to spell out foreign words (and when the words can't be exactly represented in the Japanese syllable set, you get the characteristic Japanese accent).

If this were all there was to the Japanese writing system, it would not be extremely difficult to learn. The problem is that, in addition to these two phonetic alphabets, Japanese usually uses something different for verbs, nouns, and sometimes adjectives/adverbs: the dreaded kanji. Kanji are Chinese pictographs, of which there are around 50,000, and the primary reason that learning Japanese is less fun than a root canal. Each kanji represents one particular word or idea, and the average Japanese adult needs to know around 2000 of these pictographs in order to get by.

Despite the use of Chinese pictographs, Japanese is not actually related to Chinese. The same kanji will generally mean the same thing in both Japanese and Chinese, but the spoken word for the kanji will differ. The Japanese simply decided to use the Chinese pictographs, rather than inventing a writing system from scratch. From what I've heard, the hiragana and katakana were developed after the adoption of the Chinese writing system, by aristocratic women with a substantial amount of free time, yet little formal education in writing (and, obviously, it takes a LOT of education to learn the Chinese writing system).

So, that's a simplistic overview of the Japanese writing system. I left out a number of things that I know, and there are surely things I don't. But that should give you an idea how it works, and why it's so difficult to learn (although still not as hard as Chinese, due to the fact that ALL words in Chinese are represented by pictographs, and so there are more of them to learn).

As a final note, it's thought by some that Japanese and Korean are sister languages; even from my very limited knowledge of the two languages, I can see a moderate number of words that are similar. Korean, however, uses an elegant phonetic alphabet in which each symbol represents a single sound, sort of like English (if I recall correctly, there are 14 consonants and 14 vowels in Korean). Each square kanji-looking Korean character is actually a single syllable, which is a composite of multiple sound symbols arranged in an order I don't really understand. As well, Korean does not have the same consonant-vowel-syllable structure as Japanese, and may have more than three sounds per syllable (three referring to a consonant and a diphthong, which I didn't discuss in this post). Best of all, Korean does not use (or rather, rarely uses, as at one point it did use) those terrible Chinese pictographs.

& Power Tools

So, my parents, in their infinite wisdom, have decided to add on another room to the house. Not only that, but the room will be built where the patio is, and the patio roof will become the roof of the new room. That's quite an interesting (and complicated) prospect.

In fact, we started on the first step of the process last weekend: relocating the patio roof. The plans for the room require that the patio roof be moved about two and a half feet. Considering that the roof weighs more than a ton, and is anchored into the patio concrete with sturdy metal pipes that go into the 4x4 legs, this is no small task, and took us about a day, with myself and my dad.



There were a few complications in this process. One of the four 4x4 patio legs, and part of a support beam, were eaten away by carpenter ants (making the roof itself somewhat of a safety hazard). This required attaching a large 4x6 beam to the leg to act as a support during relocation (and eventually the leg itself will be completely replaced).



2x4s were added between the roof and the legs on each corner of the roof, to reinforce the roof during transport. The legs and the pipes inside them were sawed off at the concrete, so that the roof could be moved. Very carefully, we lifted each leg onto the make-shift trolley that we would use to move the roof.

The trolley itself consisted of a bit of BC technology: two 14-foot 4x6s on top of a set of rollers, which were segments of metal piping I cut with a sawzall. This worked remarkably well, given how many thousands of years old this method is. Finally, after moving the patio, we lifted it on to large blocks cut from a 4x6 (where it currently resides), which would keep the roof high enough that we could build the walls underneath it.

Now that the roof is moved, the next phase of the project will be to convert it to the roof of an indoor room. This is not extremely difficult. Each of the 2x6s supporting the roof will be complemented with an additional 2x6 on one side, and a 2x2 on the other. In addition to reinforcing the roof, this serves to reduce the width between beams to that which may be readily filled by rolled insulation (23 inches wide).



While the relocation of the roof proceeded smoothly, a couple of humorous incidents punctuated the process, not the least of which being when my dad ended up getting a - shall we say - surprise bikini wax by a runaway electric drill (that particular model of drill has enough torque to sprain your wrist).

Bad Apples

So, if you're one of those people using OS X 10.4 on a Mac, you might want to avoid downloading Security Update 2005-007, as I hear it broke all 64 bits applications. You just know that MS is having a holiday, everyone saying "Haha, losers!"

UPDATE:
A fix for this problem was released today (8/18/2005)

& Kajiurese

As I was watching Madlax, I couldn't help but notice one really pretty song in the soundtrack. In addition to a really pretty (though quiet) melody, the lyrics were really poetic in their rhyming and meter (the chorus actually made me think of some passages in The Highwayman: another of my mom's favorites that I'd become familiar with, over the years). Some looking online revealed that the name of the song was Lost Command, on the Madlax soundtrack 2. Having identified the song, I wanted to know what the lyrics meant; boy, did that end up being more than I bargained for.

The first candidate for locating the lyrics was the insert booklet with the soundtrack; this, however, proved to be no help, as the booklet only contains the lyrics of several Madlax tracks. The next place to look was Google; this also ended in failure.

Finally, I decided I'd transcribe the lyrics and try to find somebody to translate it, myself; that was when things got really ugly. As I transcribed the lyrics, it became apparent that it was not Japanese, like some of the other songs on the Madlax soundtrack (the ones whose lyrics were included in the soundtrack booklet). So, I sent the songs to more than a dozen people I knew who spoke various languages. While I got several "that sounds kinda like [insert language that person doesn't speak, here]" ultimately all of them proved incorrect. Native speakers attested to the fact that it was not Spanish, Portuguese, French, German, Russian, Vietnamese, Hebrew, Armenian, or Czech. Second-hand speakers told me that it probably wasn't Italian, Latin, Greek, Arabic, Chinese, or any Slavic language.

So, that ruled out pretty much all major world languages, and exhausted my list of acquaintances. Now what? Well, I decided to go posting on language newsgroups. While this did not bring an answer to the question, it did bring a few clues. One person found a Japanese site which thought the lyrics were not any actual language; it was about this time that I started referring to the language as 'Kajiurese' (named after the composer, Yuki Kajiura). Another poster suggested that it might be a Creole language, or a cross between Japanese and some African language.

That was about as far as I got, and the true identify of Kajiurese (if there is one) remains unknown. However, we can do some characterization of the language. It definitely bears a resemblance to Japanese in the structure of its syllables. Each syllable is composed of a vowel, sometimes preceded by an initial consonant, and sometimes succeeded by a terminal consonant. Unlike English, where you can expect almost any ordering of letters which can be pronounced, only a handful of consonants can act as terminal consonants (this is like Japanese, where only 'n' and 's' can come without a succeeding vowel). Additionally, despite several consonants that do not occur in Japanese, Kajiurese has only 5 vowels (and a sixth which is a diphthong of the 'o' and 'u' sounds) - the very same set in Japanese. It should also be noted that the manner in which some of the terminal consonants are voiced (with both the vowel and terminating consonant sustained for a period before the next syllable) resembles how terminal consonants are pronounced in Japanese, although as some are not pronounced this way, I'm assuming that this is simply due to the Japanese accent of the singer.

After Lost Command, several other tracks in the Madlax soundtrack were identified as probably being Kajiurese (although Margaret features two sounds not seen in any of the other songs). From these songs, the following list of sounds in Kajiurese was constructed (* indicates rare sounds):

Initial Consonant	Vowel	Terminating Consonant
b ch* d h k l m n r s sh* st* s t th v y z	a e i o ou* u	n r*

Finally, the songs themselves. Syllables are delimited by apostrophes. Word breaks are not certain; they are merely my best guess where the breaks occur.

Lost Command:
Chorus:
kou ma're'a tan ba're di'tha
ko ba're'a san ma're di'tha
ha ba'ri'e'a ha ba'ri'e i di'tha
kou ma're'a tan ba're di'tha
so ba'ri'e'a sa'ba di'tha
e ba'de i'a'ra vi'da ya'ra

vi'do'ri men'ta
ha'va'na ya'ri'a
vi'do'ri men'ta ar o'o'ga

vi'de'ri men'ta
ar ka'di've'ta
de'sta'ri ven'to o'o'ga

Chorus

Madlax:
Chorus:
ka'ma'ni'a ma'di'a e'de'mi'ne'a ma'ri'a
ka'ma'ni'a so'di'a e'da'za
ke'ze sa'ma'ni'a ma'di'a e'ke'ze'na a'do'ri'a
kar ma'la'mi
sar ma'la'mi

kar'da me'a ho'za
se'ra vi'a di'a kio'za
e'ya me'a vi'a pe'za
ke'ze sar ma'la'mi
kar ma'la'mi

so'ri vi'a to'za
ve'a vi'da di'a ka'za
e'ra me'a vi'a to'za
e'ye sar ma'la'mi
ar'ka di'sa

Chorus

ka'ma'ni'a ma'di'a e'de'mi'ne'a ma'ri'a
e'ka'za
sa'ma'ni'a ma'di'a e'ke'ze'na a'do'ri'a
e'ka'za

Elanore:
Chorus:
e'sto'ra vi'tha e'ka'na'e ma
ha'vi'sta di i'kan'ta
a'do'o'ra e'ya i'sa'ma e'ra
i'vi'sa di e'ka'n'ta

Chorus

i'me'a de'ta a'no'o'ra
a'sto'ri de'tu a'do'o'ga
mi'i'da me'a a'mi'i'to
i'no'te'di no'te'di e'ya
(2 times)

Chorus

Margaret:
ko ko me'i'ta
ke'sta're go'shi'mi'o'is
i'vi'tha e'ya du'vi'a
no no che'i'ta
ke'da're no'me'ni'ta
i've'tha i'ya na'di'a
(2 times)

& Links

Added a links section to the left sidebar. All of those are either sites I visit frequently (at least daily) or the sites of my friends.

& Horror

So, yesterday I went to AnimeSuki (for those of you not into anime, AnimeSuki is one of the biggest catalogs of fan-subbed anime episodes), looking for new episodes of Mahoraba and Honey and Clover. Unfortunately, I found neither of these; but scanning the list of new releases brought something else to my eye: Great Detectives Poirot and Marple, episode 22. Heavens. Surely that can't be as bad as it sounds, right..? Unfortunately, a quick trip to ANN reveals that it is indeed an anime based on Agatha Christie's novels.

Poirot and Ms. Marple are people that I've become begrudgingly familiar with, over the years, due to my mom being a big Agatha Christie fan, and her frequently watching movie adaptations of these series on PBS, not outside my range of hearing. Somehow it disturbs me greatly that there is an anime adaptation, as well.

And There Were Two

So about 2 minutes after I posted that anime post, Jean-Francois Roy (one of my programming friends, and a legend in the Mac gaming world) informed me that his blog is now public. Depending on whether you use a Mac, Unix, or something vaguely similar, you may or may not care, as those are the primary subjects of his blog.

& Anime

Good Gord, has it been 2 1/2 weeks, already? Well I suppose I might as well post a little about my unproductive exploits, given the lack of productive ones. Let's see, where to start..? Well, predominantly, I've been watching anime, for the first time in a couple years (although I have been accumulating manga on my bookshelf over that time). After much prodding by one Magus (not that that name is distinguished enough for any of you to have any clue who I'm talking about), I watched Elfen Lied (as I already mentioned). After Elfen Lied, I watched the following (the ones that are bolded are ones I really liked, and would recommend):
- School Rumble (good series, even though the ending - or lack thereof - BLOWS)
- Air
- Madlax (interesting in a couple ways, but I wouldn't really recommend it)
- His and Her Circumstances (can't seem to find the English distributor's page for the series)
- Gunslinger Girl (while somewhat of a mass-produced anime, and lacking a central plot, I found it interesting, although I have to admit that may be because it has similarities to two of my own stories, in different ways)
- Full Metal Panic: The Second Raid (still in progress)
- Mahoraba
- Honey and Clover (still in progress; pretty amusing at times, but the lethargic pace makes it rather boring, on average)
- Banner of the Stars III
- Noir

As far as manga reading has been going, I've recently been reading the following (most of these are still in progress):
- Great Teacher Onizuka
- Cheeky Angel
- Bleach
- Yotsuba &!(this is licensed, but ADV's site is hideously outdated, and even stuff released 6 months ago isn't on there, yet)
- Elfen Lied
- Scrapped Princess (I'd recommend this anime, but as there's only one volume out, I can't really recommend the manga, yet)
- Full Metal Panic!

Of these, I want to give special recognition to Yotsuba &! That is one of the funniest series I've ever read. In fact, I've got a sample chapter uploaded here, for your viewing pleasure. Now, the series is licensed in English (and by the RIAA of the anime industry, no less...), so you can't download all the chapters (technically it isn't legal to download any of the chapters, but I figure me putting this one up here is more likely to increase their sales than decrease them...). So if you like the chapter, go buy the books!