Changes

[[Category:Fall 2019 Winter 2020 SPO600]]

<!-- {{Admon/important|It's Alive!|This [[SPO600]] weekly schedule will be updated as the course proceeds - dates and content are subject to change. The cells in the summary table will be linked to relevant resources and labs as the course progresses.}}-->

<!-- {{Admon/obsolete|[[Current SPO600 Weekly Schedule]]}} -->

|5||Feb 03||[[#Week 5 - Class I|6502 String and Memory Lab (Lab 4)]]||[[#Week 5 - Class II|Introduction to x86_64 and AArch64 architectures]]||[[#Week 5 Deliverables|Lab 54]]

|6||Feb 10||[[#Week 6 - Class I|64-bit Assembly Language 6502 String Lab (Lab 54)Continued]]||[[#Week 6 - Class II|Profilingx86_64 and AArch64 Assembly]]||[[#Week 6 Deliverables|Lab 64]]

|7||Feb 17||[[style="background:#Week 7 - Class If0f0ff"|Profiling Lab (Lab 7)]]Family Day Holiday||[[#Week 7 - Class II|Project Stage 164-bit Assembly Language Lab (Lab 5)]]||[[#Week 7 Deliverables|Lab 7, Project Profiling5]]

|8||Mar 02||[[#Week 8 - Class I|Algorithm Selection Lab (Lab 8)5 Continued]]||[[#Week 8 - Class II|SIMD and VectorizationProjects / Changing an Algorithm]]||[[#Week 8 Deliverables|Lab 5, Project Stage 1 dueBlogs]]

|9||Mar 09||[[#Week 9 - Class I|SIMD Algorithm Selection Lab (Lab 96)]]||[[#Week 9 - Class II|Identifying Optimization OpportunitiesCompiler Optimizations / SIMD and Vectorization]]||[[#Week 9 Deliverables|Lab 96]]

|10Switchover||Mar 16||[[style="background: #Week 10 - Class I|Atomics]]||[[#Week 10 - Class IIf0f0ff" colspan="5" align="center"|Project Discussion]]||[[#Online Switchover Week 10 Deliverables|Project Work]]

|1110||Mar 23||[[#Week 11 10 - Class I|Online Startup / Project HackingStage 1]]||[[#Week 11 10 - Class II|Memory Ordering, Synchronization, and BarriersReview for Stage 1]]||[[#Week 11 10 Deliverables|Project Stage 2 dueBlogging]]

|1211||Mar 30||[[#Week 12 11 - Class I|ifunc<span style="background: #ffff00;">Quiz</span> / Profiling]]||[[#Week 12 11 - Class II|Emerging directions in system architectureSIMD Part 1 - Autovectorization]]||[[#Week 12 11 Deliverables|Project WorkStage 1 due April 1, 11:59 pm / Blog about your project as you start Stage 2]]

|12||Apr 06||[[#Week 12 - Class I|SIMD Part 2 - Intrinsics and Inline Assembler]]||style="background:#f0f0ff"|Good Friday Holiday||[[#Week 12 Deliverables|Project Stage 2 due]]|-|13||Apr 0613||[[#Week 13 - Class I|Demos<span style="background: #ffff00;">Quiz</span> / Project Discussion]]||[[#Week 13 - Class II|Course wrapWrap-up discussionDiscussion]]||[[#Week 13 Deliverables|Project Stage 3 dueMonday, April 20, 11:59 pm (Firm!)]]

* ==== Strings and System Routines====** The [[6502 Emulator|6502 emulator]] has a 80x25 character display mapped starting at location '''$f000'''. Writing to a byte to screen memory will cause that character to be displayed at the corresponding location on the screen, if the character is printable. If the high bit is set, the character will be displayed in <span style="background:black;color:white;">&nbsp;reverse video </span>. For example, storing the ASCII code for "A" (which is 65 or $41) into memory location $f000 will display the letter "A" as the first character on the screen; ORing the value with 128 ($80) yields a value of 193 or $d1, and storing that value into $f000 will display <span style="background:black;color:white;">A</span> as the first character on the screen.** A "ROM chip" with screen control routines is mapped into the emulator at the end of the memory space (at the time of writing, the current version of the ROM exists in pages $fe and $ff). Details of the available ROM routines can be viewed using the "Notes" button in the emulator or on the [[6502_Emulator#ROM_Routines|emulator page]] on this wiki.** Strings in assembler are stored as sequences of bytes. As is usually the case in assembler, memory management is left to the programmer. You can terminate strings with null bytes (C-style), which are easy to detect one some CPUs (e.g., <code>lda</code> followed by <code>bne / beq</code> on a 6502), or you can use character counts to track string lengths.

* ==== Building Code====** C code is built with the C compiler, typically called <code>cc</code> (which is usually an alias for a specific C compiler, such as <code>gcc</code>, <code>clang</code>, or <code>bcc</code>).** The C compiler runs through four five steps, often by calling separate executables:**# Preprocessing - performed by the C Preprocessor (<code>cpp</code>), this step handles directives such as <code>#include</code>, <code>#define</code>, and <code>#ifdef</code> to build produce a single source code text file, with cross-references to the original input files so that error messages can be displayed correctly (e.g., an error in an included file can be correctly reported by filename and line number).**# Compilation - the C source code is converted to assembler, going through one or more intermedie representations (IR) such as [https://gcc.gnu.org/onlinedocs/gccint/GENERIC.html GENERIC] or [https://gcc.gnu.org/onlinedocs/gccint/GIMPLE.html GIMPLE], or [https://llvm.org/docs/LangRef.html LLVM IR]. The program used for this step is often called <code>cc1</code>.**# Optimization - various optimization passes are performed at different stages of processingthrough multiple passes, but centered on IR at the compilation step. Sometimes, the work of a previous pass is undone by a later pass: for example, a complex loop may be converted into a series of simpler loops by an early pass, in the hope that optimizations can be applied to one or more of the simpler loops; the loops may later be recombined to single loop if no optimizations are found that are applicable to the simplified loops.**# Assembly - converts the assembly language code emitted by the compilation stage into binary object code.**# Linking - connects code to functions (aka methods or procedures) which were compiled in other ''compilation units'' (they may be pre-compiled libraries available on the system, or they may be other pieces of the same code base which are compiled in separate steps). Linking may be static, where libraries are imported into the binary executable file of the output program, or linking may be dynamic, where additional information is added to the binary executable file so that a run-time linker can load and connect libraries at runtime.

* The source code for large projects is divided into many source files for manageability. The dependencies between these files can become complex. When developing or debugging the software, it is often necessary to make changes in one or a small number of files, and it may not be necessary to rebuild the entire project from scratch. The [[Make_and_Makefiles|<code>make</code>]] utility is used to script a build and to enable rapid partial rebuilds after a change to source code files(see [[Make and Makefiles]]). * Many open source projects distribute code as a source archive ("tarball") which usually decompresses to a subdirectory '''packageName-version''' (e.g. foolib-1.5.29). This will typically contain a script which configures the Makefile (<code>configure</code> if using GNU Autotools). After running this script, a Makefile will be available, which can be used to build the software. However, some projects use an alternative configuration tool instead of GNU Autotools, and some may use an alternate build system instead of make.* To eliminate this variation, most Linux distributions use a '''package''' system, which standardizes the build process and which produces installable package files which can be used to reliably install software into standard locations with automatic dependency resolution, package tracking via a database, and simple updating capability. For example, Fedora, Red Hat Enterprise Linux, CentOS, SuSE, and OpenSuSE all use the RPM package system, in which source code is bundled with a build recipe in a "Source RPM" (SRPM), which can be built with a single command into a binary package (RPM). The RPMs can then be downloaded, have dependencies and conflicts resolved, and installed with a single command such as <code>dnf</code>. The fact that the SRPM can be built into an installable RPM through an automated process enables and simplifies automated build systems, mass rebuilds, and architecture-specific builds.

* Blogs are due at the end of the month (Feb 2 - 11:59 pm), so proofread your posts, ensure that you have at least 1-2 per week, and make sure the link from the [[Winter 2020 SPO600 Participants|Participant's Page]] is accurate.Feel free to write multiple posts about one topic or lab, if appropriate. == Week 5 == === Week 5 - Class I ===* [[6502 Assembly Language String Lab]] (Lab 4) === Week 5 - Class II ===* Introduction to x86_64 and ARMv8a/AArch64 [[Computer Architecture|Architectures]]** [[ARMv8]] Architecture*** [[AArch64 Register and Instruction Quick Start]]** x86_64 Architecture*** [[x86_64 Register and Instruction Quick Start]]* Working with [[ELF|ELF Files]]* Compiler Options: a [[SPO600 Compiled C Lab|demo]]** -static** -g** -fno-builtin** -O0 vs -O3* Building an Open Source Project's Code** [[Make and Makefiles]] revisited** A brief introduction to GNU Autotools === Week 5 Deliverables ===* [[6502 Assembly Language String Lab|Lab 4 Results]] == Week 6 == === Week 6 - Class I ===* [[6502 Assembly Language String Lab]] (Lab 4) - Continued === Week 6 - Class II ===* x86_64 and AArch64 Assembler** See [[Assembler Basics]] === Week 6 Deliverables ===* Blog your [[6502 Assembly Language String Lab|Lab 4]] results == Week 7 == === Week 7 - Class I ===* No class - Family Day Holiday === Week 7 - Class II ===* [[SPO600 64-bit Assembler Lab]] (Lab 5) === Week 7 Deliverables ===* Blog your [[SPO600 64-bit Assembler Lab|Lab 5]] results == Week 8 == === Week 8 - Class I ===* [[SPO600 64-bit Assembler Lab|Lab 5]] Continued === Week 8 - Class II ===* [[Winter 2020 SPO600 Project|Course Projects]]** Building software** Benchmarking * Changing an Algorithm to Improve Performance** Audio volume scaling problem*** PCM Audio is represented as 16-bit signed integer samples*** To reduce the volume of the audio, it can be scaled by a factor from 0.000 (silence) to 1.000 (original volume).*** This is a common operation on mobile and multimedia devices.*** What is the best way to do this?** Approach 1: Naive Implementation - Multiply each sample by the scaling factor (this involves multiplying each integer sample by a floating-point number, then converting the result back to an integer)** Approach 2: Lookup Table - Pre-calculate all possible values multiplied by the scaling factor, then look up the new value for each original sample value** Approach 3: Fixed-point math - Use fixed-point math rather than floating-point math** Approach 4: Vector fixed-point math - Use SIMD instructions to do multiple fixed-point operations in parallel === Week 8 Deliverables ===* Blog your [[SPO600 64-bit Assembler Lab|Lab 5]] results.* '''Reminder:''' Blogs are due for February this Sunday (March 8, 11:59 pm). == Week 9 == === Week 9 - Class I ===* [[SPO600 Algorithm Selection Lab]] (Lab 6) === Week 9 - Class II ===[[Winter 2020 SPO600 Project|project]]* [[Compiler Optimizations]]* SIMD and Vectorization** [[SPO600 Vectorization Lab|Optional vectorization lab]] === Week 9 - Deliverables ===* Blog about [[SPO600 Algorithm Selection Lab|Lab 6]] and your Project == Week 10 == === Week 10 - Class I ===* [https://youtu.be/DCp8oghdTfU Video - March 23]* Focus this week: Complete Stage 1 of your [[Winter 2020 SPO600 Project|Course Projects]] === Drop-in Online Discussion Sessions ===* Tuesday to Friday (March 24-27) from 9-10 AM* Online at https://whereby.com/ctyler** There is a maximum of 12 people in the room at a time. I recommend dropping by one or twice a week with your questions.** If 9-10 am cannot work for you, email me to discuss this. === Week 10 - Class II ===* [https://youtu.be/M-5IizEwkfY Video - March 27: Review of material for Stage 1]* Stage 1 due date '''extended''' to Wednesday, April 1, 11:59 pm === Week 10 - Deliverables ===* Blog about your [[Winter 2020 SPO600 Project|project]]. Project Stage 1 is due next Wednesday. == Week 11 == === Week 11 - Class I ===* Quiz #4 - Online in Blackboard* '''Optional video:''' [https://youtu.be/CdyERanIxmI Building Software] - This video provides a review of building an open-source software package from either a source archive (zip or tarball) or from a code repository (such as a <code>git</code> repository).* [https://youtu.be/Hip1KtYZKE0 Video - March 30: Profiling Software]** Profiling with <code>gprof</code> and <code>perf</code> === Week 11 - Class II ===* [https://youtu.be/EIPbufXhiQs Video - April 3: SIMD and Auto-vectorization]* SIMD-Autovectorization Resources** [https://gcc.gnu.org/projects/tree-ssa/vectorization.html Auto-Vectorization in GCC] - Main project page for the GCC auto-vectorizer.** [http://locklessinc.com/articles/vectorize/ Auto-vectorization with gcc 4.7] - An excellent discussion of the capabilities and limitations of the GCC auto-vectorizer, intrinsics for providing hints to GCC, and other code pattern changes that can improve results. Note that there has been some improvement in the auto-vectorizer since this article was written. '''This article is strongly recommended.'''** [https://software.intel.com/sites/default/files/8c/a9/CompilerAutovectorizationGuide.pdf Intel (Auto)Vectorization Tutorial] - this deals with the Intel compiler (ICC) but the general technical discussion is valid for other compilers such as gcc and llvm === Week 11 Deliverables ===* [[Winter 2020 SPO600 Project|Project Stage 1] due Wednesday, April 1 (yes, really) at 11:59 pm* Blog about your project as you continue into Stage 2** March posts are due on Monday, April 6 at 11:59 pm. == Week 12 == === Week 12 - Class I ===* [https://youtu.be/76rtxPozPJI Video - April 6: SIMD, Inline Assembler, and Compiler Intrinsics]** [[Inline Assembly Language]]** [[Compiler Intrinsics]] * Retired SPO600 Labs - These labs are not being used this semester but may be useful for reference. The software in these labs was used in the video for this week.** [[SPO600 SIMD Lab]]** [[SPO600 Inline Assembler Lab]] === Week 12 - Class II ===* No class - Good Friday === Resources ======= Auto-vectorization ====* [https://gcc.gnu.org/projects/tree-ssa/vectorization.html Auto-Vectorization in GCC] - Main project page for the GCC auto-vectorizer.* [http://locklessinc.com/articles/vectorize/ Auto-vectorization with gcc 4.7] - An excellent discussion of the capabilities and limitations of the GCC auto-vectorizer, intrinsics for providing hints to GCC, and other code pattern changes that can improve results. Note that there has been some improvement in the auto-vectorizer since this article was written. '''This article is strongly recommended.'''* [https://software.intel.com/sites/default/files/8c/a9/CompilerAutovectorizationGuide.pdf Intel (Auto)Vectorization Tutorial] - this deals with the Intel compiler (ICC) but the general technical discussion is valid for other compilers such as gcc and llvm==== Inline Assembly Language ====* [[Inline Assembly Language]]* [http://developer.arm.com ARM Developer Information Centre]** [https://developer.arm.com/products/architecture/a-profile/docs/den0024/a ARM Cortex-A Series Programmer’s Guide for ARMv8-A]* The ''short'' guide to the ARMv8 instruction set: [https://www.element14.com/community/servlet/JiveServlet/previewBody/41836-102-1-229511/ARM.Reference_Manual.pdf ARMv8 Instruction Set Overview] ("ARM ISA Overview")* The ''long'' guide to the ARMv8 instruction set: [https://developer.arm.com/docs/ddi0487/latest/arm-architecture-reference-manual-armv8-for-armv8-a-architecture-profile ARM Architecture Reference Manual ARMv8, for ARMv8-A architecture profile] ("ARM ARM")==== C Intrinsics - AArch64 SIMD ====* [https://developer.arm.com/architectures/instruction-sets/simd-isas/neon/intrinsics ARM NEON Intrinsics Reference]* [https://gcc.gnu.org/onlinedocs/gcc/ARM-C-Language-Extensions-_0028ACLE_0029.html GCC ARM C Language Extensions] == Week 13 == === Week 13 - Class I ===* [https://youtu.be/GLzAVWW8dEo Video - April 16: Project Stage 3] === Week 13 - Class II ===* Wrap-up Session