Exploring Parallel Caesar Cipher Implementation in RISC-V

The Ides of RISC-V Writing & Testing a Parallel Caesar Cipher in RISC- V Will Hawkins he/him/his hawkinsw@gmail.com @hawkinsw 1

Outline - - - - Introduction About RISC-V About the Caesar Cipher Caesar Cipher Implementations - Sequential - Parallel Uniqueness of RISC-V Vector Extensions Spike - a RISC-V Emulator - Emulating the Application - Debugging the Application Questions and Discussion - - - 2

Introduction - Assumptions: - You have an interest in the topic. - You have minimal familiarity with computer architecture. - You will ask questions in the chat or afterward if you are confused. - You will correct me when, not if, I am wrong. All code is online: - Spike, a RISC-V Emulator - GCC/Binutils for RISC-V - pk, RISC-V Proxy Kernel - Caesar Cipher Implementation and Installation Tool(s) Who am I? - I am a software developer and computer scientist in the United States. - I am a long-time free software user/contributor. - I am a learner of new things. - - 3

About RISC-V - An instruction set architecture (ISA) - cf. Intel x86, ARM. Unlike x86, it has a reduced instruction set. - CISC: Make a grilled cheese sandwich. - RISC: - Set location to the pantry. - Walk to location - Set target to the door. - Open target. - etc. Unlike ARM and x86 it IS FREE AND OPEN. - Instruction Sets Should Be Free: The Case For RISC-V Work began on RISC-V in 2010. - Lineage from the 80s beginning with David Patterson s research at Berkeley. - - - 4

Caesar Cipher - This cipher is named after Julius Caesar, who is said to have used this simple cipher to communicate with his army. The sender and receiver share a key, a shift distance. The sender encodes the message by shifting each letter forward shift difference. The receiver decodes the message by shifting each letter backward shift distance. peace - - - Plaintext: Ciphertext: qfbdf Encode: next letter Decode: previous letter 1https://www.cia.gov/news-information/featured-story-archive/2007-featured- story-archive/cracking-the-code.html 5

Caesar Cipher: Sequential Implementation P E A C E Single instruction, single data. 112 101 97 99 101 +1 +1 +1 +1 +1 113 102 98 100 102 Q F B D F 6

Caesar Cipher: Parallel Implementation P E A C E Single instruction, multiple data. 112 101 97 99 101 +1 +1 +1 +1 +1 113 102 98 100 102 Q F B D F 7

Vector Operations: Single Instruction, Multiple Data Vector 0 A B C D E Multiple data Vector 1 F G H I J Add Vector 0 to Vector 1; Store the result in Vector 2 Single instruction Vector 2 A + F B + G C + H D + I E + J 8

Vector Operations: The Traditional ISA Perspective 16 16 16 16 bits Vector register (from vector system v) 32 bits bits 64 bits bits 32 bits bits vadd32, vsub32, etc. vadd16, vsub16, etc. 9

Vector Operations: The Traditional ISA Perspective A vector register (from vector system v) 64 bits That escalated quickly. vadd32, vsub32, etc. vadd16, vsub16, etc. 16 16 16 16 16 16 16 16 bits A vector register (from vector system x) 32 bits bits 64 bits bits 32 bits bits 128 bits bits 32 bits bits 64 bits bits 32 bits bits xadd64, xsub64, etc. xadd32, xsub32, etc. xadd16, xsub16, etc. 1https://www.sigarch.org/simd-instructions-considered-harmful/ 10

Vector Operations: The RISC-V ISA Perspective That s more like it. 16 16 16 16 16 16 16 16 bits Vector register 32 bits bits 64 bits bits 32 bits bits N bits bits 32 bits bits 64 bits bits 32 bits bits vset vadd, vsub, vmul, etc. 11

Caesar Cipher: The RISC-V Implementation Plain text 8 t 8 e 8 s 8 t N bits bits bits bits bits 1. Configure the vector Key N bits8 8 1 8 1 8 1 2. Load the plain text 1 bits bits bits bits 3. Load the key Ciphertext 4. Encrypt N bits8 8 f 8 t 8 u u bits bits bits bits 5. Store the ciphertext 12

Caesar Cipher: Demonstration 13

Why the emulator? 1. Easy to test 2. Lack of available RISC-V hardware a. Available to me. b. The GAPuino c. The HiFive Unmatched d. The BeagleV 3. Vector operations are not standardized yet! a. Current status 14

System Overview: Building Host computer (x86 or ARM) Caesar Cipher Application Executable Caesar Cipher Application Source Code RISC-V assembler and compiler 15

System Overview: Executing Host computer (x86 or ARM) Spike-emulated RISC-V Guest Caesar Cipher Application Executable Proxy Kernel 16

System Overview: Boot reset init_first_hart boot_loader enter_supervisor_mode Time Proxy Kernel rest_of_boot_loader run_loaded_program start_user Caesar Cipher Application Executable start main User Mode Supervisor Mode Machine Mode 17

System Overview: Debugging - Spike gives a GDB-like debugging interface - Breakpoints: - Unconditional: until pc <core> <val>: Run until the instruction counter on core <core> reaches address <val>. - Conditional: until mem <addr> <val>: Run until the memory at address <addr> matches value <val>. until reg <core> <reg> <val>: Run until the register <reg> on core <core> matches value <val>. - Memory inspection: - Look at registers: reg <core> [reg]: Show the values of the register file on core <core>. Optionally include a [reg] that specifies which register to inspect. - Look at memory: mem <addr>: Show the value of memory at address <addr>. 18

System Overview: Debugging, an example reset init_first_hart boot_loader enter_supervisor_mode Time Proxy Kernel rest_of_boot_loader run_loaded_program start_user Caesar Cipher Application Executable start main User Mode Supervisor Mode Stop at beginning of main. Machine Mode 19

System Overview: Debugging, a demonstration - While there are breakpoints in Spike, they operate a little differently than in gdb. - In Spike, we cannot define a breakpoint using a symbol. - We can only define a breakpoint at a memory address. Therefore, we have to find the address of main in memory to set the breakpoint. - Do as I do, not as I say. 20

Conclusion - - - About RISC-V Caesar Cipher Caesar Cipher Implementations - Sequential - Parallel Uniqueness of RISC-V Vector Extensions Spike - a RISC-V Emulator - Emulating the Application - Debugging the Application - - 21

Questions and Discussion 22