Bitstuff

For people interested in how computers work bottom-up.

Friday, February 09, 2007

Subtract and Branch if Negative

I got pretty bored over winter break, and decided I needed a project to keep me busy until class started. Well, there was one thing that I've been wanting to do for a long time. I have wanted to build a simple computer out of 7400 series logic chips. I only had about a week for the whole project, so the design had to be pretty spartan. I also wanted to use chips that I had on hand, though that didn't last for too long.

After thinking up a few different ideas, I finally remembered another project that I've been wanting to do: build a Subtract and Branch if Negative computer. That is, a computer whose only instruction is to subtract two numbers, store the result, and branch to an alternative memory location if the result is negative. This is very much like SBN on wikipedia.

If you don't care to look at the Wikipedia page, the subtract and branch if negative instruction turns out to be the only instruction you need to build a turing-complete computer. That is, this one instruction, given enough time and memory, can compute anything that a regular computer can. Of course, it's slow, inefficient, and a pain to program.

So I went about designing a simple microcomputer based on this instruction. First step, I needed to decide on some basic specifications for the processor:

Data Width: 8-Bits
Address Space: 16-Bits
Instruction Set: Subtract and Branch if Negative

After that, I could rough out a block diagram of the dataflow. Using the dataflow as a guide, I figured out what chips I could use in what blocks, how many I would need and how they connect to each other.

The dataflow was the easy part. More difficult is designing the control logic, which was going to be especially complicated because of the 8 and 16 bit busses. This is because it now requires two cycles to read in the address of an operand, and another cycle to read in the value of the operand. This needs to be done once for both operands, and then again when we need to load the new PC value if the instruction takes the branch.

The control sequence for the processor goes something like this:
  1. Load MAR.H; PC++
  2. Load MAR.L; PC++
  3. Load B
  4. Load MAR.H; PC++
  5. Load MAR.L; PC++
  6. Load A
  7. Store ALU Result; PC++
  8. Load PC.L
  9. If (ALU Result is negative) {Load PC}
A pretty reasonable way to encode the control logic would be to program the control signals into an EEPROM. This is very simple and is easier to change if there is a bug. However, I had never used EEPROMs before, so I decided to build a state machine out of 7400 series logic. It's a bit of a mess, and there were a few bugs to squash, but it works.

So we have the control and the dataflow...what else? Input and output. There needs to be a way to load programs onto the device, and then a method of interacting with the running program.

I had initially thought about using a series of switches for loading programs into RAM. That was going to be incredibly tedious and time consuming, so I scratched that. Instead, I did some research on the Parallel port, and found it to be the perfect solution. It's easy to interface, easy to program and completely automated. This only required a few extra chips to interface the parallel port to the system bus on the microcomputer. Basically, it needs to be able to take control of the bus when it needs to program, and relinquish control when it's done.

Last bit of hardware, the human machine interface. I have to admit, it's pretty craptacular on this microcomputer. An 8-bit dipswitch and an 8-LED bargraph are all the I/O you get. However, this fits in with the overall strategy of making somewhat rediculous design decisions. There is however, at least one neat trick that can be done to expand the output capabilities.

The fabrication of this computer is another story. I had hoped I would be able to build it on a printed circuit board, that would have been wonderful. However, I had too many chips for the free version of Eagle CAD I had. Simply would not fit on the board. So I decided to use a pre-drilled perferated board with solder pads. Good enough, but wiring ended up taking most of the week. Luckily for you, you don't have to wait to see the finished product. The final stage of the microcomputer has two boards. The bottom board has the processor, memory, power supply and clock generator. The top board holds the batteries, has some blinky lights, dip switch and some simple address decode logic for memory-mapped IO.

To wire up all the parts, I used a lot of wire-wrap wire, solder and a wire-wrap tool. The leads on the parts were very short, so wire-wrapping was a real pain, but it seemed to be the best way to get the leads into place for soldering. It was slow going and took about four very full days to finish. On top of that, I had to test and debug different parts as I finished them. It can make you pretty nervous when you have to desolder several connections on one IC to make a fix.

If I do another 7400 series-based microcomputer, I will get a proper wire-wrap board.

Now that the darn thing is built, what to do? The work's not done yet. After building and debugging it, I still needed to be able to write, assemble and load programs. I needed to write an assembler and program loader.

The program loader actually turned out to be the easiest part of the whole project. Programming the parallel port on Linux was much easier than I expected. In fact, the loader program only had one bug in it the first time I tried it. Made the fix, tried it again, worked!

Now that I could load any data I wanted into the microcomputer's memory, I needed an easier way to program it. This meant developing a simple two-pass assembler. On top of that, I wanted it to have some built-in pseudo operations, so I could program and still keep my sanity. Programming this device with only using the low-level subtract and branch if negative instruction is not my cup of tea.

Eventually I hacked out a simple assembler that fit the bill. The assembly code looks like this:

sub i, imm(-10)
loop:
dec i
bltz i, loop

This little snippet is a simple loop. It subtracts -10 from i (which it assumes to be 0), setting up the number of iterations. Each iteration it decrements the loop index, and continues to loop as long as "i" is greater than or equal to zero.

Each instruction in that snippet is a pseudo-operation that is converted into SBN instructions by the assembler. Furthermore, each of those pseudo-ops can be converted into exactly one SBN instruction.

The "imm(-10)" bit of code allows me to operate with immediate values in my code. All it does is return the address of the value"-10" on the constant table. These keeps me from having to allocate a memory location for each constant I use in my code.

I now have everything I need to write a demo program. I wanted the microcomputer to do something unexpected. Something you wouldn't think it would be able to do. I think the most limiting part of it is it's input and output. I decided the demo would be an output-only program. This leaves me with eight blinky lights to do something cool with.

So, the most unexpected thing to do, would be to project an image with those eight lights. That's my thought anyways. I was set on displaying a smiley face using just those lights. How, you might ask, can that be done? Using persistance of vision.

If you've ever looked at a flashlight in the dark, you've probably noticed that it seems to leave a trail when you look at it. If you spin it in a circle fast enough, you might see a circle of light, neato. The idea behind displaying a smiley face on the eight lights is the same. If I move the lights, or use a mirror to move them, your eyes will see a trail marking where that light has been in your field of vision. If we setup a regular motion of a mirror, and display one line of the image at a time, we can display an entire 2D image using one line of eight lights.

So that's what I did. The program outputs one line of the desired image, blanks the lights for a split second, the next line is lit up, and so on. I took a picture of the effect with my camera. I don't have any mirrors yet, so I just panned the camera across the lights in the dark, it worked out really well. To show other people, I can just shake the lights up and down. Eventually, I would like to get a small mirror, motor and switch for synchronization. That seems a bit safer than shaking the fragile computer.

In the end what I got is an 8-Bit computer with one instruction, 32 KB of RAM and a clock speed of 250KHz. Though it takes nine cycles to execute one instruction, so in reality, it's executing about 28,000 instructions per second.

55 Comments:

Blogger Ross said...

This comment has been removed by the author.

12:22 AM  
Blogger Ross said...

I simply don't know what to say.... besides.... most impressive

12:24 AM  
Blogger ozamosi said...

*drewl* I want one!

One question: is there any way to get the schematics and/or the software (assembler and parallell port communication software)?

5:54 AM  
Blogger Luke said...

The schematics are written in colored pencil on several sheets of paper. So it may take a bit of work to get those into order.

The source code is easier, and I'll find a way to post it.

6:01 PM  
Blogger XANi said...

Very impressive :D
Build 32 version and run linux on it ;]

10:47 AM  
Blogger John said...

This looks like a fantastic project, I'd be interested in seeing the schematics.

I'd love to try something similar which can communicate back to the PC over the parallel port.

6:18 AM  
Blogger NPolynomial said...

Very cool! I once built a brainfuck processor using TTL chips.

I'm looking forward to building new architectures someday and have been considering the OISC for a while now...

http://novaconceptions.blogspot.com

2:31 PM  
Blogger NPolynomial said...

Well, I don't know how to follow your blog, would you be interested in a link swap with me? We seem to write about similar subjects and we have the same layout background.

Take care,

Jesse

2:34 PM  
Blogger 三合 said...

你的部落格很棒,我期待更新喔........................................

8:09 PM  
Blogger 走吧 said...

從人生中拿走友誼,猶如從生活中移走陽光........................................

6:35 AM  
Blogger 春天來嚕 said...

nice job! waiting for your new artical. ........................................

1:38 AM  
Blogger 皓云 said...

I love readding, and thanks for your artical.........................................

4:14 AM  
Blogger 楊偉誠 said...

how do u do?................................................................

4:29 PM  
Blogger 羅惠玲 said...

唯有學習不已的老師,才能認真的教,唯有燃燒自己,才能點亮他人的燈......................................................

9:35 PM  
Blogger G702aynelleKress0 said...

高聊天室ut男同聊天同志聊天至聊天室uut男同志聊天av99洪爺影城av99影片亞洲av99影片金瓶梅影片av99影片洪爺avdvd168影片av女優線上免費看av女優論壇av免費情色短片av免費電影av免费电影av亞洲成人區av直播台av直播式av看影片av動畫卡通av專賣店av情色網站排行榜av情色影片免費觀賞av情圖貼av援交妹av免費區AV免費看短片av色貼圖av女優館av片直播辦公室偷情遊戲免費視訊聊天網ut聊天室聊天室

11:04 AM  
Blogger 香君 said...

性愛性交性愛線上性愛線上看女優性愛性愛照85成人文學85成人片免費觀看85c免費影城85c免費成人85c成人片免費85cc文章85cc成人片觀賞85cc成人影片免費成人片觀看!85cc免費片85cc免費卡通片85cc免費影片長片播放85cc免費觀看外國片85cc洪爺85cc無碼a片85cc無碼片觀看85cc無碼影片85cc影片觀看外國85cc論談85成人影城85成人論壇85街自拍85街短片85街歐美影城85貼圖區85遊戲凹凸色色卡通圖片免費即時通視訊85cc成人片觀看交友戀愛進行室

11:04 AM  
Blogger BurtonClary031 said...

喜樂的心是健康良藥,憂傷的靈使骨枯乾。........................................

1:26 AM  
Blogger 銘雅婷木 said...

快樂是你與生俱來的權力,它不應該取決於你完成什麼。 ..................................................

2:40 AM  
Blogger 淑娟 said...

幸福是人人都要,又怎麼可能都歸你所有?要知道這世界幸福本來就不多........................................

6:30 PM  
Blogger 韋于倫成 said...

性愛淫蕩淫慾淫亂淫婦淫妹淫叫淫水淫女情慾情色做愛限制級波霸口交18禁貼圖寫真視訊援交露點爆乳潮吹裸體裸照裸女愛愛無碼尋夢視訊聊天a漫a片a圖一夜情

1:02 PM  
Blogger 昭彥 said...

援交友聊天室 成人視訊jaanli 視訊聊天交友1758 素人自拍,情色小站 av999電影院 a片 男同志網gay圖片 咆哮老鼠concert 高雄寂寞小站 成人情色 視訊21sex 176視訊聊天室 avdvd情色影片 love104 視訊聊天室 摸摸耳小遊戲 1111非常好色6 0下載 情人輔助品視訊交友 成人視訊ynbcom 情色a片-情色小站 aio交友愛情館 18x us視訊聊天 內衣名模寫真 南人情色論壇 東東成人論談 xxvideo 倉井空免費a影片 免費視訊173liveshow google台灣 賓館偷拍影片 s383情色大網咖 歐美潮吹短片 104視訊美女 0951撥打電話下載 0204免費下載短片 免費視訊交友 援交情人視訊聊天室 avdvd免費無碼a片 視訊網愛聊天室85cc yam天空影音 104川藏第一美女視訊 無碼視訊情色小站 色美媚,洪爺的家 杜雷斯免費影片 網愛交友網 視訊甜心寶貝av貼片區 aio辣妺視訊 東京熱情色影片 交友網愛戀之旅 上班族酒趴網 免費視訊monico sex520貼片

1:40 AM  
Blogger 韋于倫成 said...

18禁貼圖寫真視訊援交露點爆乳潮吹裸體裸照裸女愛愛無碼尋夢視訊聊天a漫a片a圖一夜情一葉情人妻激情情色寫真美女自拍辣妹自拍正妹自拍美女走光辣妹走光正妹走光脫衣秀脫衣走光色情自慰自拍

9:38 AM  
Blogger 建銘建銘 said...

原來這世上能跟你共同領略一個笑話的人竟如此難得 ............................................................

10:13 PM  
Blogger Dorath政儒yN_ said...

A liar is not believed when he speaks the truth...................................................

5:09 AM  
Blogger saa said...

成人線上卡通 視訊網 正妹聊天 免費成人圖 交友援 av女優寫真貼圖 漫畫性感美女 微風線上影片 自拍.偷拍 ut聊聊天室 成人視訊 情趣用品 18禁卡通遊戲 巨乳美少女 咆曉小咾鼠影城 免費a片 線上觀看情色影片 免費線上觀看色情 一夜情人 383成人影音成 sexygirl 裸照 虐待美女 辣妹寫真集dvd 淫亂人妻日記 歐美熟女色情圖片 免費視訊 空姐圖貼 69成人a圖下載 微風寫真館 85cc影 微風論壇情色 嘟嘟 xo777 情色性愛貼圖 台北援交網 嘟嘟情色網 鋼管秀 下載av 洪爺娛樂往 台灣大奶影片 sexy888影片分享區 下載 巨乳人妻初體驗h漫 台灣性愛文學網 後宮18jack 限制級國片 0204成人 免費性愛觀看 走光

9:46 PM  
Blogger 宛齊陳 said...

到處逛逛~~來繞繞留個言囉~~~~.................................................................

4:35 PM  
Blogger 林奕廷 said...

一隻穿雲箭 千軍萬馬來相見 這麼棒的文章 幫你頂先!

5:29 PM  
Blogger 常映 said...

Pen and ink is wits plough. .................................................................                           

7:26 AM  
Blogger 吳思 said...

生存乃是不斷地在內心與靈魂交戰;寫作是坐著審判自己。......................................................................

7:26 AM  
Blogger 郁雨郁雨 said...

幸福不是一切,人還有責任。....................................................................

8:16 PM  
Blogger 啟均 said...

向著星球長驅直進的人,反比踟躕在峽路上的人,更容易達到目的。............................................................

6:27 AM  
Blogger 鄭湘定 said...

人生是故事的創造與遺忘。............................................................

2:20 AM  
Blogger 芳容222許林堅林芳容儀 said...

要照顧身體歐~保重..................................................................

8:51 AM  
Blogger 婉婷 said...

安安唷~~幸運的日子送給妳(你)滿滿的幸福,也祝福你天天都開心唷..................................................................

11:23 AM  
Blogger 吳婷婷 said...

想要推動天下,先要發動自己。..................................................................

9:08 PM  
Blogger 茹希茹希 said...

逛街不如逛部落格,省錢又開心啊............................................................

3:40 AM  
Blogger 宋瑞正宋瑞正 said...

Poverty tries friends.............................................................

7:12 PM  
Blogger 陳佑發 said...

Share and share alike.............................................................

8:54 AM  
Blogger 思恬 said...

i consder your artical is so nice!............................................................

2:47 AM  
Blogger 朱正恆朱正恆 said...

唯有學習不已的老師,才能認真的教,唯有燃燒自己,才能點亮他人的燈............................................................

11:23 PM  
Blogger 淑李娟 said...

來給你加油,幫你推一下喔~期待你的下一個更新,謝謝............................................................

2:00 AM  
Blogger 靜詹怡詹詹 said...

很精彩的部落格 期待你的繼續加油............................................................

2:00 AM  
Blogger 黃怡張華樺張華樺妹 said...

More haste, less speed..................................................................

4:50 AM  
Blogger 凱v胡倫 said...

等很久了 謝謝你的用心............................................................

12:21 AM  
Blogger 邱思吳佳順翰 said...

Poverty tries friends...................................................................

8:01 PM  
Blogger 鄭雅雯 said...

肯定與支持你!!!加油囉~..................................................

3:33 AM  
Blogger 麗王王珠 said...

人生匆匆-把握當下,支持鼓勵~事事如意~..................................................

4:36 PM  
Blogger 阿袁袁袁袁華 said...

好熱鬧喔 大家踴躍的留言 讓部落格更有活力..................................................

4:36 PM  
Blogger 翊翊翊翊張瑜翊翊翊 said...

我來湊熱鬧的~~^^ 要平安快樂哦............................................................

6:47 PM  
Blogger 江仁趙雲虹昆 said...

你的部落格不錯哦,我來享受一下~~..................................................................

10:19 PM  
Blogger 建枫 said...

原來天鵝嫁給癩蛤蟆就會生出醜小鴨。。。

4:27 AM  
Blogger 欣侑欣侑欣侑欣侑 said...

It is no use crying over spilt milk.......................................................................

7:34 PM  
Blogger Mathieu said...

Aw man, I wanted to build something like this for a while... This is amazing :-°. I will definitely give it a go as soon as I am settled.

Cheers

2:52 AM  
Blogger alkopop79 said...

Amazing job!

6:05 PM  
Blogger Will Gilreath said...

Hello Luke, (sorry for length...couldn't find e-mail address for you...)

I was searching the web for material relating to the search keywords of “one instruction computer” or “single instruction computer” (ultimate RISC, minimal instruction set) and found your website with a one-instruction computer that you had developed and explored--very interesting and impressive.

I’m curious about what caught your interest in the concept of a one-instruction computer? And, if you have done further work on the project/concept?

My message/questions are of mutual interest in the notion of one-instruction computers. I am William Gilreath, the lead author of a computer architecture book that explored much of the history, background, and concepts of one-instruction computers. The book is “Computer Architecture: A Minimalist Perspective” published in 2003, and there is a website about the book at http://www.caamp.info.

One possibility I am considering is a webpage on the CAAMP website with third-party implementations and projects. If you have no objection, I’d like to link to your project webpage. If you do not want that, all is well (or more simply, “that’s cool, no harm, no foul”, but if you do, that’d be great.

Thanks, my best, and keep up the good work on your webpage about OISC.

William Gilreath
http://www.williamgilreath.com

9:47 PM  

Post a Comment

<< Home