COMPUTER ALGORITHMS AND ARCHITECTURE - 2017/8

Module code: EEE2048

Module provider

Electrical and Electronic Engineering

Module Leader

GUILLEMAUT J Dr (Elec Elec En)

Number of Credits

15

ECT Credits

7.5

Framework

FHEQ Level 5

JACs code

Module cap (Maximum number of students)

N/A

Module Availability

Semester 1

Overall student workload

Assessment pattern

Assessment type Unit of assessment Weighting
Coursework COURSEWORK (2 MARKED ITEMS) 25%
Examination 2 HOUR CLOSED-BOOK WRITTEN EXAMINATION 75%

Alternative Assessment

n/a

Prerequisites / Co-requisites

None

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 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

Attributes Developed
Write basic pseudo-assembly code for a common processor (C,P). CP
Explain the key design principles of microprocessors (C). C
Analyse processor and memory performance (C). C
Describe the data and control paths within a processor (K). K
Create a simple high-level design of a large software system represented through UML models (P) P
Analyse the processing performance of algorithms and characterise this using Big-Oh notation (C) C
Implement solutions to some simple logical problems using recursion (P) P
Appropriately select, and justify the selection of, data structures and algorithms for some logical problems (C) C
Describe and program in pseudo-code some well-known abstract data types (K,P) KP
Be able to explain the operation of some common algorithms for data handling and describe them using pseudo-code (K) K
Be able to implement some well-known algorithms and abstract data types using C code (K,P) KP

Attributes Developed

C - Cognitive/analytical

K - Subject knowledge

T - Transferable skills

P - Professional/Practical skills

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

Methods of Teaching / Learning

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


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.
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.
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.
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.
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)

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

Reading list

Reading list for COMPUTER ALGORITHMS AND ARCHITECTURE : http://aspire.surrey.ac.uk/modules/eee2048

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 2017/8 academic year.