COMPUTER ALGORITHMS AND ARCHITECTURE - 2020/1

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

Electrical and Electronic Engineering

Module Leader

GUILLEMAUT Jean-Yves (Elec Elec En)

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

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

[2 - 3]     MIPS Instruction Set Architecture. Arithmetic instructions. Load and store instructions.  Instruction formats. Decision making instructions.

[4]          Assessing and understanding microprocessors performance. Definition of performance. Performance metrics. Benchmarks. Examples.

[5]          Building a 32-bit arithmetic logic unit for the MIPS architecture.

[6 - 7]     Simplified implementation of the MIPS datapath. Single-cycle datapath implementation.  Multi-cycle approach. Control signals. Control unit implementation. Examples.

[8]          Enhancing CPU performance with pipelining. Pipelined datapath. Pipeline control.       Dependencies. Forwarding. Stalling. Branch hazards.

[9 - 10]   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.

 

Part B - Algorithmic Programming and Software Design

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

[4]          Building code: testing and debugging

[5-7]       Recursion:  problem decomposition; base cases; implementation examples; run-time 

              tracing; program efficiency issues: iteration versus recursion; recurrence relations

[9-12]       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;

[13-14]   Searching: directed and controlled scanning and implications of data ordering; hashing: hash functions and collision handling

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

[18]        Software development lifecycle: stages; methodologies.

[19-20]   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, and analyse various data structures and algorithms. The coursework will assess skills at implementing data structures and algorithms using C code, and ability to analyse those implementations. Software development lifecycle and OO analysis and design will be introduced via small-group and class discussion of a case-study of a large software system.

 

Thus, the summative assessment for this module consists of:

• 2 hour closed-book written examination


• Programming assignment. An assignment to implement data structures and/or algorithms using C code, and then obtain run-time results of the execution of the code, as well as analysis of those results. Deliverables are the C code as well as a report to describe the program, and detail results with analysis. Coursework is set in Week 5, and due in on Tuesday of Week 9.

 

Any deadline given here is indicative. For confirmation of exact dates and times, please check the Departmental assessment calendar issued to you.

 

Formative assessment and feedback

 

For the module, students will receive formative assessment/feedback in the following ways.

• During lectures, by small-group problem-solving exercises and class-discussion of solutions.


• By means of unassessed tutorial problem sheets. Solutions to these are presented during class-discussion sessions in lectures, as well as on model solutions being available on SurreyLearn.


• During supervised computer laboratory sessions


• Via assessed coursework

Via small-group and class-discussion of a large software system design

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 introduction, in-class exercises and computing laboratory session on “Big-Oh”, the students will be able to analyse algorithms and compare the performance of different algorithms.


2. Through the introduction, in-class exercises 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 introduction, in-class exercises 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 booklet provides about 30 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.


5. Through small-group and class discussions of a case-study of the design of a large software system, students will be introduced to the basics of software design of large systems, using a case-study of a UML design of such a system.

 

Learning and teaching methods include the following.

 

• Lectures, small-group exercises and class discussions, 30 hours (spread over 10 weeks)


• Computing laboratory sessions, 10 hours (spread over 10 weeks)

Revision sessions 3 hours (week 11)

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 2020/1 academic year.