BSc, Beng and MEng Degree Examinations 2020–21 DEPARTMENT OF COMPUTER SCIENCE
System and Devices 1 Open Assessment
Issued:
Submission due: Feedback and Marks due:
12:00 noon Wednesday 21st April 2021 12:00 noon Wednesday 12th May 2021 12:00 noon Monday 9nd June 2021
All students should submit their answers through the electronic submission system: http://www.cs.york.ac.uk/student/assessment/submit/
An assessment that has been submitted after this deadline will be marked initially as if it had been handed in on time, but the Board of Examiners will normally apply a lateness penalty.
Your attention is drawn to the section about Academic Misconduct in your Departmental Handbook: https://www.cs.york.ac.uk/student/handbook/.
All queries on this assessment should be drawn to: • Dr Mike Freeman (mjf@cs.york.ac.uk).
Answers that apply to all students will be posted on the VLE.
COM00011C
Page 1 of 9
SYS1 Open Assessment 2020/21
This assessment continues the work started in practical 9. When answering these questions you must use the assembler and ISE project files from the Exam folder on the VLE.
The bug trap’s functionality and accuracy are to be further improved by the addition of a camera. To implement the required bug detection algorithms a number of new software routines are required. Your task is to implement these functions. Where required new instructions and additional hardware may be added to improve processing performance. However, to ensure compatibility with other systems the following restrictions are imposed:
• The maximum clock speed used by the system is limited to 10MHz.
• Instruction names and machine code implementations i.e. bit fields used, are
restricted to those defined in Appendix A.
• The assembler simpleCPUv1d_as.py may not be modified.
• Only a single macro file : simpleCPUv1d.m4 may be used.
• The following ISE files may not be altered:
◦ CPU test-bench – cpu_tb.vhd
◦ Computer schematic – computer.sch
◦ Processor schematic – simple_cpu_v1d.sch ◦ Memory model – ram_4Kx16_sim_v1a.vhd
• Input images are limited to the file : bug24×24.ppm which can be downloaded from the Exam folder on the VLE.
• Output images are limited to 24×24 pixels in size and must use the PPM or PGM image formats, as defined in each question.
The component symbols used in the schematic simple_cpu_v1d may not be altered e.g. DATA_MUX, COUNTER_12, ALU, REGISTER_FILE_4 etc. However, the hardware within these components can be modified e.g. you can not alter the ALU symbol, but you can add additional processing elements to the ALU schematic.
Note, if the external interfaces of these components are altered you will be awarded a zero mark for the questions affected.
You may implement any of the instructions defined in Appendix A. However, you do not need to do so to complete the programming tasks in questions 2,3 or 4. There are also two undefined instructions XOP1 (immediate) and XOP2 (register). You are free to modify the ALU and DECODER to implement new functionality for these undefined instructions. This functionality may be changed to suit the processing requirements of each question. The assembler simpleCPUv1d_as.py has already been updated to support these new instructions and may not be altered.
At the end of each question there is a description of the files that you need to submit. These files should be placed in a directory of the same name i.e. Q1, Q2, Q3, or Q4. When complete these directories should be compressed into a single file: SYS1.zip and uploaded through the submission system.
Page 2 of 9
COM00011C
Q1 (10 marks)
To detect overflows during unsigned additions a new conditional jump instruction is required. This instruction should use the instruction format shown in figure 1. If the carry flag in the status register is set the processor should jump to the absolute address specified in the instruction, otherwise the program counter should be incremented to the address of the next instruction.
Figure 1 : conditional jump instruction
The file decoder.vhd has been updated to implement this new instruction and can be tested using the test code shown in Appendix B. The assembler simpleCPUv1d_as.py has already been updated to support this new instruction.
Write out the RTL descriptions of the micro-instructions used to perform this instruction during the Fetch, Decode and Execute phases, and briefly describe its operation. You should also identify what components / signals are used and the modifications made to the file decoder.vhd. These descriptions must be submitted as a plain text file named: jumpc.txt.
Submission: for this question you should submit one file : jumpc.txt. Do not submit the full ISE project. Files that do not comply to the stated file formats will be awarded a zero mark.
COM00011C
Page 3 of 9
Q2 (10 marks)
Mark centre : write a program to place a red cross in the middle of an RGB image stored in memory, as shown in figure 2. The centre of the image is define as co- ordinate position (11,11). This image is stored in memory using the packed RGB data type shown in figure 3. For more information on this data type refer to practical 9. This program must be named : markCentre.asm and submitted as a plain text file.
Figure 2 : mark centre subroutine output. FEDCBA9876543210
7654376543276543
Figure 3 : 16-bit packed RGB data format
The memory model ram_4Kx16_sim has already been configured to automatically load the tested image: bug24x24.ppm and store it at base address 1024. When your program has finished processing this image it must store the value 0x00 to address 0xFFF to trigger the generation of the output image file: output.ppm.
Your program must be capable of processing an image in 2.5 us, programs not meeting this minimum requirement will be awarded a zero mark.
Submission: for this question you should submit:
• markCentre.asm : a plain text file, assembly language program used to
implement the mark centre functionality. You may also submit a single macro
file : simpleCPUv1d.m4 if used.
• Any ISE schematics (.sch files) that have been modified to implement this
system.
• Any new ISE schematics (.sch files) and symbols (.sym files) that have
been created to implement this system.
• The file decoder.vhd if you have implement any new instructions.
Note, remember you are not allowed to modify the top level schematics, as defined on page 2.
These files will be added to the base ISE project from the Exam folder on the VLE for testing. Do not submit the full ISE project. The output image will be regenerate
COM00011C
Page 4 of 9
during the marking process. Files that do not comply to the stated file formats will be awarded a zero mark.
Q3(40 marks)
Encrypt : write a program to encrypt RGB image data using a simple block cipher. Encryption is performed on each pixel in two steps. First swap the nibbles in the high and low bytes as shown in figure 4.
Figure 4 : pixel data nibble swap
Next, each bit position is inverted by subtracting the swapped data from 0xFFFF, as shown in the example in figure 5. The resulting encrypted data is then written to memory.
1111111111111111
– 1101101001011101
0010010110100010
Figure 5 : bit inversion
This program must be named: encrypt.asm and submitted as a plain text file. Again, the memory model ram_4Kx16_sim has already been configured to automatically load the tested image: bug24x24.ppm and store it at base address 1024. When your program has finished processing this image it must store the value 0x00 to address 0xFFF to trigger the generation of the output image file: output.ppm.
To test if your encryption program has worked correctly the python program decrypt.py can be downloaded from the VLE. This will decrypt the encrypted PPM image output.ppm to produce a new file call new.ppm.
Your program must be capable of processing an image in 15 ms, programs not meeting this minimum requirement will be awarded a zero mark. Full marks will only be awarded if the program is capable of processing an image in less than 1.22 ms.
The maximum execution time can be achieved using software only solutions. To achieve higher processing speeds new instructions and supporting hardware components will need to be added to the processor, as outlined in practical 9.
Note, these instructions must comply to the restrictions outlined on page 2. Submission: for this question you should submit:
COM00011C
Page 5 of 9
• encrypt.asm : a plain text file, assembly language program used to implement the encryption functionality. You may also submit a single macro file : simpleCPUv1d.m4 if used.
• Any ISE schematics (.sch files) that have been modified to implement this system.
• Any new ISE schematics (.sch files) and symbols (.sym files) that have been created to implement this system.
• The file decoder.vhd if you have implement any new instructions.
Note, remember you are not allowed to modify the top level schematics, as defined on
page 2.
These files will be added to the base ISE project from the Exam folder on the VLE for testing. Do not submit the full ISE project. The output image will be regenerate during the marking process. Files that do not comply to the stated file formats will be awarded a zero mark.
The awarded mark for this question is determined by a solution’s functionality and processing performance i.e. the mark will be inversely proportional to execution time, ranging from 20 marks for solutions meeting the maximum timing requirements, to 40 marks for solutions matching or exceeding the minimum timing requirements.
Page 6 of 9
COM00011C
Q4 (40 marks)
image = [ ]
new = [ ]
j = 1024
FOR i IN RANGE 1600 to (1600+288)
LOOP
new[i] = Y(image[j+1])<<8 || Y(image[j]) j=j+ 2
END LOOP
save( new )
Figure 6 : pseudo code
Generate PGM : write a program to implement the pseudo code shown in figure 6. An initial solution to this problem is discussed on :
http://simplecpudesign.com/simple_cpu_v1d_image/index.html
You are required to optimise this solution’s processing performance and modify its implementation to meet the restrictions stated on page 2.
This code converts RGB image data stored in memory into a grayscale image i.e. the function Y( ). Each new pixel value is represented as an unsigned 8-bit value. Two pixels are packed into each memory location using “little-endian” format i.e. the first pixel is stored in the lower byte position. The grayscale image must be stored in memory at base address 1600.
The brightness of each pixel should be calculated using the perceived brightness (Y) equation :
Y = 3R + G + B 828
You may use different algorithms to calculate brightness, however, the brightness of each pixel must be within +/- 10% of the reference image output.pgm. This image can be downloaded from the VLE. The output image must use the PGM image format. Solutions not meeting these requirements will be awarded a zero mark.
This program must be named: grayscale.asm and submitted as a plain text file. Again, the memory model ram_4Kx16_sim has already been configured to automatically load the tested image: bug24x24.ppm and store it at base address 1024. When your program has finished processing this image it must store the value 0x00 to address 0xFFF to trigger the generation of the output image file: output.pgm.
Note, as previously specified the grayscale image must be stored at base address 1600, with two pixel values stored in each memory location.
COM00011C
Page 7 of 9
Your program must be capable of processing an image in 225 ms, programs not meeting this minimum requirement will be awarded a zero mark. Full marks will only be awarded if the program is capable of processing an image in less than 1.82 ms.
The maximum execution time can be achieved using software only solutions. To achieve higher processing speeds new instructions and supporting hardware components will need to be added to the processor, as outlined in practical 9.
Note, these instructions must comply to the restrictions outlined on page 2.
Submission: for this question you should submit:
• grayscale.asm : a plain text file, assembly language program used to
implement the grayscale functionality. You may also submit a single macro
file : simpleCPUv1d.m4 if used.
• Any ISE schematics (.sch files) that have been modified to implement this
system.
• Any new ISE schematics (.sch files) and symbols (.sym files) that have
been created to implement this system.
• The file decoder.vhd if you have implement any new instructions.
Note, remember you are not allowed to modify the top level schematics, as defined on page 2.
These files will be added to the base ISE project from the Exam folder on the VLE for testing. Do not submit the full ISE project. The output image will be regenerate during the marking process. Files that do not comply to the stated file formats will be awarded a zero mark.
The awarded mark for this question is determined by a solution's functionality and processing performance i.e. the mark will be inversely proportional to execution time, ranging from 5 marks for solutions meeting the maximum timing requirements, to 40 marks for solutions matching or exceeding the minimum timing requirements.
Page 8 of 9
COM00011C
Appendix A : SimpleCPUv1d instruction-set
# INSTR # MOVE # ADD # SUB # AND
# LOAD # STORE # ADDM # SUBM
# JUMPU # JUMPZ # JUMPNZ # JUMPC
# CALL
# OR # XOP1
# RET # MOVE # LOAD # STORE # ROL
# ROR # ADD # SUB # AND # OR # XOR # ASL
# XOP2 # NU # NU # NU
IR15 IR14 0 0
0 0
0 0
0 0
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
1 1
1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
IR13 IR12 0 0
0 1
1 0
1 1
0 0 0 1 1 0 1 1
0 0 0 1 1 0 1 1
0 0
0 1 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
IR11 IR10 IR09 IR08 IR07 RD RD X X K RD RD X X K RD RD X X K RD RD X X K
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A
A A A A A
RDRDX X K RD RD X X K
X X X X X RD RD RS RS X RD RD RS RS X RD RD RS RS X RSDRSDX X X
RSDRSDX X X RDRDRSRSX RDRDRSRSX RDRDRSRSX RDRDRSRSX RDRDRSRSX RSDRSDX X X
RDRDRSRSX RDRDRSRSX RDRDRSRSX RDRDRSRSX
IR06 IR05 K K
K K
K K
K K
A A A A A A A A
A A A A A A A A
A A
K K K K
X X X X X X X X X X
X X X X X X X X X X X X X X
X X X X X X X X
IR04 IR03 K K
K K
K K
K K
A A A A A A A A
A A A A A A A A
A A
K K K K
X 0 X 0 X 0 X 0 X 0
X 0 X 0 X 0 X 1 X 1 X 1 X 1
X 1 X 1 X 1 X 1
IR02 IR01 IR00 K K K
K K K
K K K
Appendix B : JUMPC test code
start:
move ra 0xff
jumpc fail
add ra 0x1
jumpc pass1
fail:
jump fail
pass1:
add ra 0x1
jumpc fail
pass2:
jump pass2
# load register ra 0xFFFF
# carry flag not set, no jump
# add 1 to generate carry
# carry flag set, jump
# fail, trap
# add 1 no carry generated
# carry flag not set, no jump
# pass, trap
Page 9 of 9
K K K
A A A A A A A A A A A A
A A A A A A A A A A A A
A A A
K K K K K K
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0
1 0 1 1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1
1 0 0 1 0 1 1 1 0 1 1 1
-- NOT IMPLEMENTED
-- NOT IMPLEMENTED -- NOT IMPLEMENTED
-- NOT IMPLEMENTED -- NOT IMPLEMENTED -- NOT IMPLEMENTED -- NOT IMPLEMENTED -- NOT IMPLEMENTED -- NOT IMPLEMENTED -- NOT IMPLEMENTED
-- NOT IMPLEMENTED -- NOT USED
-- NOT USED
-- NOT USED
COM00011C