COMPUTER ALGORITHMS AND ARCHITECTURE - 2022/3

Module Overview

Module purpose:  this module is organized into two parts that run concurrently. Part A introduces the students to microprocessors. This covers the key concepts in microprocessor organization and design; specifically for the instruction set, performance analysis, the arithmetic logic unit (ALU), and the processor control and data paths. Additionally, we explore common memory hierarchies and caching problems. In class problems are given as examples in design.

Part B covers the analysis, design and implementation of computer algorithms. It presents concepts and methods for the analysis of algorithms. Classic programming techniques and data-structures needed to develop efficient algorithms in C for solving logical and data-handling problems are introduced, and students will attend programming lab sessions where they have the opportunity to implement in C the algorithms that have been covered. The software development lifecycle is introduced and the various methodologies described. Techniques for the design of large and complex software are introduced through the use of UML.

Module provider

Computer Science and Electronic Eng

Module Leader

GUILLEMAUT Jean-Yves (CS & EE)

Number of Credits: 15

ECTS Credits: 7.5

Framework: FHEQ Level 5

Module cap (Maximum number of students): N/A

Module Availability

Semester 1

Prerequisites / Co-requisites

None

Module content

Indicative content includes the following.

Part A  - Microprocessor Organisation and Design

• Introduction. Computer abstractions and technology. The changing face of computing. Embedded microprocessors. Instructions: language of the computer.


• MIPS Instruction Set Architecture. Arithmetic instructions. Load and store instructions.  Instruction formats. Decision making instructions.


• Assessing and understanding microprocessors performance. Definition of performance. Performance metrics. Benchmarks. Examples.


• Building a 32-bit arithmetic logic unit for the MIPS architecture.


• Simplified implementation of the MIPS datapath. Single-cycle datapath implementation. Multi-cycle approach. Control signals. Control unit implementation. Examples.


• Enhancing CPU performance with pipelining. Pipelined datapath. Pipeline control. Dependencies. Forwarding. Stalling. Branch hazards.


• Exploring memory hierarchy. Direct mapped cache. Memory organization. Decreasing miss ratio with associativity. Example implementation: 4-way associative cache. Virtual memory. Making address translation fast. Modern microprocessors systems. Examples.

• Analysis of algorithms: characterisation of problem data-size and program running time; big-O notation; asymptotic behaviour; typical running times.


• Building code: testing and debugging.


• Recursion: problem decomposition; base cases; implementation examples; run-time tracing; program efficiency issues: iteration versus recursion; recurrence relations.


• Data structures: revision of simple data-types and pointers; abstract data-types: implementation and use of singly linked lists, doubly linked lists, stacks, queues, trees, binary trees binary search trees.


• Searching: directed and controlled scanning and implications of data ordering; hashing: hash functions and collision handling.


• Sorting: elementary sort algorithms: selection, insertion, bubble; implications of initial ordering of data;  quick sort; merge sort; priority queues, binary heaps and heap sort.


• Software development lifecycle: stages; methodologies.


• OO Analysis and Design: Functional modelling: use cases; Structural modelling: CRC cards, class diagrams, object diagrams; behaviour modelling: sequence diagrams, behavioural state machine diagrams.

Assessment pattern

Alternative Assessment

n/a

Assessment Strategy

The assessment strategy for this module is designed to provide students with the opportunity to demonstrate the learning outcomes. The written examination will assess knowledge of design principles and features of processors, as well as the ability to write basic pseudo-assembly code for a common processor and to analyse processor and memory performance. The written examination will also assess knowledge of, and ability to describe using pseudo-code or C code, and analyse various data structures and algorithms. This is complemented by a number of formative assessment and feedback activities including computer laboratory sessions, as well as exercises and tutorials performed either in class or in a self-guided fashion.

The summative assessment for this module consists of:

• 2 hour invigilated written examination.

• As part of exercises provided within the lecture materials, with model solutions provided on SurreyLearn,


• By means of tutorial problem sheets. Solutions to these are presented during class-discussion sessions in lectures/tutorials, with model solutions provided on SurreyLearn,


• During supervised computer laboratory sessions,


• As part of revision activities such as working through past exam papers or through formative online tests.

Module aims

• Microprocessors have penetrated everyday life – from our smart-phones to our cars. Understanding the operations of a common microprocessor and how it is designed provides the students with skills to analyse and comments on physical processor architectures. This module aims to present the MIPS processor design and its evolution, from basic reduced instruction set languages, such as assembly, through to complex memory systems and co-processors.
• Programming is a skill which many electronic engineers find themselves needing at some point during their career, whether this be designing and building a new software system or, at the other end of the spectrum, implementing a new digital filter in software before translating it to hardware. This module will provide students with the necessary skills to be able to design and program algorithms, and to be able to analyse the performance of their algorithm.
• Students will secure programming skills learned during the previous year by implementing programs in C with more complicated requirements than previously, and learn advanced programming techniques essential to anyone wishing to pursue software development further in their career.

Learning outcomes

Methods of Teaching / Learning

The learning and teaching strategy is designed to achieve the following aims:

1. Through the lectures, exercises/tutorials and computing laboratory session on “Big-O”, the students will be able to analyse algorithms and compare the performance of different algorithms.


2. Through the lectures, exercises/tutorials and computing laboratory session on recursion, students will learn several algorithm design paradigms enabling them to design and implement solutions to appropriate problems.


3. Through the lectures, exercises/tutorials and computing laboratory sessions on data structures, searching and sorting, students will learn to implement various algorithms for the solution of data-handling problems.


4. The lecture materials include a range of exercises and tutorials covering the full breadth of the module; students will be able to pace their own learning in parallel with the lecture course, and at various points solutions will be worked through in class-discussions, as well as being available on SurreyLearn.

• Pre-recorded lectures;


• Summary lectures;


• Tutorials;


• Self-guided exercises or tests with worked solutions;


• Computing laboratory sessions;


• Revision sessions.

Indicated Lecture Hours (which may also include seminars, tutorials, workshops and other contact time) are approximate and may include in-class tests where one or more of these are an assessment on the module. In-class tests are scheduled/organised separately to taught content and will be published on to student personal timetables, where they apply to taken modules, as soon as they are finalised by central administration. This will usually be after the initial publication of the teaching timetable for the relevant semester.

Reading list

https://readinglists.surrey.ac.uk
Upon accessing the reading list, please search for the module using the module code: EEE2048

Programmes this module appears in

Please note that the information detailed within this record is accurate at the time of publishing and may be subject to change. This record contains information for the most up to date version of the programme / module for the 2022/3 academic year.