|
|
|
Twist for project 7/8 - Memory costs money
|
This twist is for project 8 but you should start thinking of it before starting project 7.
As you know, our computer has limited memory (it can only load and run programs that have no more than 32768 HACK instructions). Naive implementations of the VMTranslator program will typically generate, for a simple game like Pong, around 60000 HACK instructions. This of course means that using such a VMTranslator will prevent us from running this game on our computer and having the joy of seeing the code generated by us actually working.
Your twist is to build your VMTranslator in such a way that will reduce the amount of HACK instructions that are generated. This should be done by optimizing the way your VMTranslator works.
Our way of checking it is to see if the supplied Pong VM program, after being translated by your VMTranslator and assembled, is able to run on our computer, meaning that it will not have more than 32768 HACK instructions.
More specifically:
- We'll open the following tar (contains the Pong and the OS VM files) into a directory.
- We'll run YOUR VMTranslator on that directory.
- We'll run OUR Assembler.sh on the asm file that was generated in the previous step.
- We'll check that the Pong.hack generated in the previous step actually works on the CPUEmulator (and behaves like the Pong game).
- We'll count the number of instructions (lines) in that Pong.hack file.
Please notice that:
- Even though this twist is an integral part of the VMTranslator it shouldn't affect the main function of the VMTranslator. We will still check that it translates VM to ASM which behaves as expected using other programs shorter than the Pong game.
- Failing to achieve the goal of translating the Pong game into no more than 32768 HACK instructions will cause reduction of up to 25 points - it's better to have a VMTranslator that completely works than to achieve this goal.
- You should not create any CompactASM code, this will cause our Assembler to fail.
- We ask you again to work only within the pair, please also check that you don't send clues in the news-group
Some tips:
- If you try to run our Assembler on asm files with more than 32768 assembly instructions it may fail to run claiming that the program is too large (indeed, how do you expect to jump to a label whose address can not be given with an A-Instruction?). Counting the lines in such an asm file while ignoring empty lines / comments / labels should give you the number of hack instructions this file would've been translated to and thus help you estimate how far away you are from your goal.
- Add comments to the ASM file you create - it'll help you debug your code and better understand the way your ASM file works.
- Some of the ASM commands can be replaced with fewer commands, for example: @0 , D=A => D=0.
- Some of the VM commands can be replaced with fewer ASM commands, for example, try to understand why "gt, if-goto ABC" (why is this a common pattern?) can be implemented with less ASM commands than "add, if-goto ABC" (hint: JGT) while in a naive implementation the first pattern is typically implemented with more ASM instructions than the second.
Bonus:
Prof. Nisan offered a perfect grade in this course to any pair whose generated Pong will have less than 16490 HACK instructions, as long as they hand in all of the rest of the projects and get an average of 85 on them.
This goal was achieved by Yannai & his exercise partner Ori Peleg in this course. It was very hard, but this shows that it is possible to achieve this goal within the time frame you have to work on it.
| |