Introduction to Computing

(CS111)

Junar A. Landicho

junarlandicho@ustp.edu.ph

“

The only limit to our realization of tomorrow will be our doubts of today.

Franklin D. Roosevelt

Topic 2:

Data

Manipulation

IT 416

Information Systems Development and Management

Learning Outcomes

By the end of this topic, students will be able to: Describe the variety of abstractions used to represent data.

Explain how binary sequences are used to represent digital data.

Identify multiple levels of abstractions that are used when writing programs.

Explain how programs implement algorithms.

Use abstraction to manage complexity in programs.

CS 111 – Introduction to Computing

Overview

1. Computer Architecture

2. Machine Language

3. Program Execution

4. Arithmetic/Logic Instructions 5. Communicating with Other Devices 6. Programming Data Manipulation 7. Other Architectures

CS 111 – Introduction to Computing

Computer Architecture Java

PHP

Python

CS 111 – Introduction to Computing

Computer Architecture

Central Processing Unit (CPU) ▪ Arithmetic/Logic Unit

▪ Control Unit

▪ Register Unit

o General purpose registers

oSpecial purpose registers

Bus

Main Memory

CS 111 – Introduction to Computing

CPU Basics

CPU and main memory connected via a bus

CS 111 – Introduction to Computing

Stored Program Concept

A program can be encoded as bit patterns and stored in Main

Memory. From there, the Control Unit can extract, decode, and

execute instructions.

Instead of rewiring the CPU, the program can be altered by

changing the contents of Main

Memory.

CS 111 – Introduction to Computing

Machine Language Java

PHP

Python

CS 111 – Introduction to Computing

Machine Language

Machine instruction: An instruction

encoded as a bit pattern

recognizable by the CPU

Machine language: The set of all

instructions recognized by a

machine

CS 111 – Introduction to Computing

Machine Language Philosophies

Reduced Instruction Set Computing

(RISC)

▪ Few, simple, efficient, and fast

instructions

▪ Examples: PowerPC from

Apple/IBM/Motorola and ARM

Complex Instruction Set Computing

(CISC)

▪ Many, convenient, and powerful

instructions

▪ Example: Intel

CS 111 – Introduction to Computing

Machine Instruction Types

Data Transfer: copy data from one

location to another (e.g. LOAD,

STORE)

Arithmetic/Logic: operations on bit

patterns

(e.g. +, -, *, /, AND, OR, SHIFT,

ROTATE)

Control: direct the execution of the

program

(e.g. JUMP, BRANCH)

CS 111 – Introduction to Computing

Vole: An Illustrative Machine Language

Adding values stored in memory

Dividing values stored in memory

The architecture of the Vole

CS 111 – Introduction to Computing

Parts of a Machine Instruction

Op-code: Specifies which operation to execute Operand: Gives more detailed information about the operation ▪ Interpretation of operand varies depending on op-code

CS 111 – Introduction to Computing

Parts of a Machine Instruction

Decoding the instruction 0x35A7

Decoding the instruction 0x35A7

CS 111 – Introduction to Computing

Program Execution Java

PHP

Python

CS 111 – Introduction to Computing

Program Execution

Controlled by two special purpose registers ▪ Instruction register (holds current instruction) ▪ Program counter (holds address of next instruction)

Machine Cycle: (repeat these 3 steps) ▪ Fetch, Decode, Execute

CS 111 – Introduction to Computing

The Machine Cycle

CS 111 – Introduction to Computing

Decoding the InstructionCS 111 – Introduction to Computing

An Example of Program Execution

Stored in main memory ready for execution

CS 111 – Introduction to Computing

An Example of Program Execution Performing the fetch step of the machine cycle

CS 111 – Introduction to Computing

Arithmetic/Logic Instructions

Python

Java

PHP

CS 111 – Introduction to Computing

Arithmetic/Logic Instructions

Logic Operations:

▪ AND, OR, XOR

▪ often used to mask an operand

Rotation and Shift Operations:

▪ circular shift, logical shift, arithmetic shift

Arithmetic Operations:

▪ add, subtract, multiply, divide

▪ two’s complement versus floating-point

CS 111 – Introduction to Computing

Arithmetic/Logic Instructions

Logic Operations:

▪ AND, OR, XOR

▪ often used to mask an operand

Rotation and Shift Operations:

▪ circular shift, logical shift,

arithmetic shift

Arithmetic Operations:

▪ add, subtract, multiply, divide

▪ two’s complement versus floating

point_{Rotating the bit pattern 0x65 one bit to the right}

CS 111 – Introduction to Computing

Communicating with Other Devices

Python

Java

PHP

CS 111 – Introduction to Computing

Communicating with Other Devices

Controller: handles communication

between the computer and other

devices

▪ Specialized (by type of device)

▪ General purpose (USB, HDMI)

Port: The point at which a device

connects to a computer

Memory-mapped I/O: devices

appear to the CPU as though they

were memory locations

CS 111 – Introduction to Computing

Communicating with Other Devices

Controllers attached to a machine’s bus

CS 111 – Introduction to Computing

Communicating with Other Devices

A conceptual representation of memory-mapped I/O

CS 111 – Introduction to Computing

Communicating with Other Devices

Direct memory access (DMA):

Main memory access by a

controller over the bus

▪ Von Neumann Bottleneck: occurs

when the CPU and controllers

compete for bus access

Handshaking: the process of

coordinating the transfer of data

between the computer and the

peripheral device

CS 111 – Introduction to Computing

Communicating with Other Devices

Popular Communication Media

▪ Parallel Communication: Several

signals transferred at the same time,

each on a separate “line”

(computer’s internal bus)

▪ Serial Communication: Signals are

transferred one after the other over a

single “line” (USB, FireWire)

CS 111 – Introduction to Computing

Data Communication Rates

Measurement units

▪ bps: bits per second

▪ Kbps: Kilo-bps (1,000 bps)

▪ Mbps: Mega-bps (1,000,000 bps)

▪ Gbps: Giga-bps (1,000,000,000 bps)

Bandwidth: Maximum available

rate

CS 111 – Introduction to Computing

Programming Data Manipulation

Python

Java

PHP

CS 111 – Introduction to Computing

Programming Data Manipulation

Programing languages shields

users from details of the machine:

▪ A single Python statement might

map to one, tens, or hundreds of

machine instructions

▪ Programmer does not need to know

if the processor is RISC or CISC

▪ Assigning variables surely involves

LOAD, STORE, and MOVE op-codes

CS 111 – Introduction to Computing

Bitwise Problems as Python Code

print(bin(0b10011010 & 0b11001001))

# Prints '0b10001000'

print(bin(0b10011010 | 0b11001001))

# Prints '0b11011011'

print(bin(0b10011010 ^ 0b11001001))

# Prints '0b1010011'

CS 111 – Introduction to Computing

Control Structures

If statement:

if (water_temp > 140):

print('Bath water too hot!’)

While statement:

while (n < 10):

print(n)

n = n + 1

CS 111 – Introduction to Computing

Functions

Function: A name for a series of operations that

should be performed on the given parameter or

parameters

Function call: Appearance of a function in an

expression or statement

x = 1034

y = 1056

z = 2078

biggest = max(x, y, z)

print(biggest) # Prints '2078'

CS 111 – Introduction to Computing

Functions

Argument Value: A value plugged into a

parameter

Fruitful functions return a value

void functions, or procedures, do not return a

value

sideA = 3.0

sideB = 4.0

# Calculate third side via Pythagorean

Theorem

hypotenuse = math.sqrt(sideA**2 + sideB**2)

print(hypotenuse)

CS 111 – Introduction to Computing

Input / Output

# Calculates the hypotenuse of a right triangle

import math

# Inputting the side lengths, first try

sideA = int(input('Length of side A? '))

sideB = int(input('Length of side B? '))

# Calculate third side via Pythagorean Theorem

hypotenuse = math.sqrt(sideA**2 + sideB**2)

print(hypotenuse)

CS 111 – Introduction to Computing

Sample Python Script

# Marathon training assistant.

import math

# This function converts a number of minutes and # seconds into just seconds.

def total_seconds(min, sec):

return min * 60 + sec

# This function calculates a speed in miles per hour given

# a time (in seconds) to run a single mile. def speed(time):

return 3600 / time

CS 111 – Introduction to Computing

Sample Python Script (cont)

# Prompt user for pace and mileage.

pace_minutes = int(input('Minutes per mile? ')) pace_seconds = int(input('Seconds per mile? ')) miles = int(input('Total miles? '))

# Calculate and print speed.

mph = speed(total_seconds(pace_minutes, pace_seconds)) print('Your speed is ' + str(mph) + ' mph')

# Calculate elapsed time for planned workout. total = miles * total_seconds(pace_minutes, pace_seconds) elapsed_minutes = total // 60

elapsed_seconds = total % 60

print('Your elapsed time is ' + str(elapsed_minutes) + ' mins ' + str(elapsed_seconds) + ' secs')

CS 111 – Introduction to Computing

Sample Python Script (cont) Example Marathon Training Data

CS 111 – Introduction to Computing

Other Architectures Java

PHP

Python

CS 111 – Introduction to Computing

Other Architectures

Technologies to increase throughput:

Pipelining: Overlap steps of the machine cycle

Parallel Processing: Use multiple processors

simultaneously

▪ SISD: Single Instruction, Single Data (No parallel

processing)

▪ MIMD: Multiple Instruction, Multiple Data (Different

programs, different data)

▪ SIMD: Single Instruction, Multiple Data (Same

program, different data)

CS 111 – Introduction to Computing

CS 111 – Introduction to Computing

</End>