Algoritmizace a programování

Algoritmizace a programování

Struktura počítače

České vysoké učení technické Fakulta elektrotechnická Ver.1.10

J. Zděnek 2015

Struktura předmětu • • • • • • • • • • • • • •

Systémová struktura počítače, procesor, paměti, periferní zařízení Systém přerušení, zpracování asynchronních událostí Algoritmy, programy, programovací jazyky, jazyk C Proměnné, typy, operátory, výrazy, příkazy, vstup a výstup Řízení běhu programu, řídící struktury Struktura programu v C, podprogramy a funkce Předávání parametrů (hodnotou, odkazem), reentrantní funkce Procedurální programování Pole, struktury a uniony Ukazatele a ukazatelová aritmetika Soubory, standardní knihovny Algoritmy vyhledávání a řazení, rekurze Preprocesor, podmíněný překlad, makra, hlavičkové soubory Specifika programování vestavěných (Embedded) systémů

A8B14ADP Algoritmizace a programovaní - Struktura počítače

2

Zdroje informací • •

Přednášky k předmětu A8B14ADP Web předmětu A7B14SAP • http://motor.feld.cvut.cz • Literatura [1] Kernighan, B.W. - Ritchie, D.M.: Programovací jazyk C, Computer Press, Brno 2006. ISBN: 97880251089702. [2] Harbison, S.P.- Steele, G.L.: A Reference Manual 5th ed. Prentice Hall 2002. ISBN: 978-01308959293. [3] Herout, P.: Učebnice jazyka C. 6. vyd. Kopp 2010. ISBN: 978-80-7232-383-84. [4] Herout, P.: Učebnice jazyka C - 2.díl, 4. vyd. Kopp 2010. ISBN: 978-80-7232-367-85. [5] Wróblenski, P.-Michalek, M.-Kiszka, B: Algoritmy. Datové struktury a programovací techniky. ComputerPress, 2004. ISBN: 80-251-0343-9


3

Učební pomůcky (software) •

Integrované vývojové prostředí pro OS Windows nebo Linux • IDE NetBeans s instalací kompilátoru pro jazyk „C” • http://www.netbeans.org (instalace pro studenty zdarma)

• •

Integrované vývojové prostředí pro OS Windows IDE MPLAB s instalací kompilátoru pro jazyk „C“, (Microchip C18) • http://www.microchip.com (instalace pro studenty zdarma)


4

Systémová struktura počítače - úvod

Struktura počítače


5

Architektura počítače - hardware Hlavní komponenty počítače

Paměť programu a dat

Vstupní a výstupní zařízení

Komunikace s okolním světem

Procesor Výpočetní část Mezipaměť výsledků Řízení Řadič (Controller)


6

Architektura typu „von Neumann“ Společná paměť programu (instrukcí) a dat

NELZE paralelně číst instrukce a přenášet data (cesta je společná)


7

Architektura typu „von Neumann“ • • • • • • • •

•

Instrukce a data jsou uložena v téže paměti. Instrukce a data nelze přenášet po sběrnici současně (společná cesta) – pomalejší činnost Jednodušší propojení procesoru s pamětí Paměť je organizována lineárně (tzn. jednorozměrně) a je rozdělena na stejně velké buňky, které se adresují celými čísly (zprav. 0, 1, 2, 3, . . . ). Data ani instrukce nejsou explicitně označeny. Explicitně nejsou označeny ani různé datové typy. Pro reprezentaci dat i instrukcí se používají dvojkové signály. Instrukce se provádějí jednotlivě, a to v pořadí, v němž jsou zapsány v paměti, pokud není toto pořadí změněno speciálními instrukcemi (nazývanými skoky). Počítač tvoří: Processor (ALU – aritmetická a logická jednotky, registry, řídicí část (řadič – controller), hlavní paměť (main memory) – společně instrukce a data, systém přerušení, vstupní a výstupní zařízení (periferie – peripherals)


8

Architektura typu „Harvard“ Oddělená paměť programu (instrukcí) a dat

LZE paralelně číst instrukce a přenášet data (cesty jsou oddělené) A8B14ADP Algoritmizace a programovaní - Struktura počítače

9

Architektura typu „Harvard“ • • • • • • • •

•

Instrukce a data jsou uložena v oddělených pamětech. Instrukce lze číst současně s přenosem dat (oddělené cesty) – rychlejší činnost Šířka přenosové cesty instrukcí může být jiná (větší) než přenosová cesta dat. Složitější propojení procesoru s pamětmi (vs „von Neumann“) Data a instrukce jsou explicitně označeny Paměť je organizována lineárně (tzn. jednorozměrně) a je rozdělena na stejně velké buňky, které se adresují celými čísly (zprav. 0, 1, 2, 3, . . . ). Pro reprezentaci dat i instrukcí se používají dvojkové signály. Instrukce se provádějí jednotlivě, a to v pořadí, v němž jsou zapsány v paměti, pokud není toto pořadí změněno speciálními instrukcemi (nazývanými skoky). Počítač tvoří: Processor (ALU – aritmetická a logická jednotky, registry, řídicí část (řadič – controller), paměť programu (instrukcí), paměť dat, systém přerušení, vstupní a výstupní zařízení (periferie – peripherals)


10

Vývoj software – úrovně abstrakce

Literatura: [1] A8B14ADP Algoritmizace a programovaní - Struktura počítače

11

Vývoj software – úrovně abstrakce if( z < 0 || z > 35} x++; else y++;

1

cmp bnc cmp bc inc

2

Překladač (sw) z, #0 Cont1 z, LIM Cont1 x

Asembler (sw) 1001 0011 0101 0001 0110 1101 0011 1010 0001 1110 1100 0011 0111 0010 1010 0001 0101 1110 0010 0011

3

Processor (hw) *WR *RD

4

DB A8B14ADP Algoritmizace a programovaní - Struktura počítače

12

Organizace hlavní (operační) paměti počítače •

Hlavní paměť je rozdělena na buňky – paměťová místa, kterým jsou přiřazena nezáporná čísla nazývaná adresy

•

• Obsah paměťového místa je slovo • slovo (word) – velikost závisí na procesoru (např. 16b, 24b, 32b, 64b), • b – značí bit (binary digit) • B – značí byte (slabika), 8b = 1B, byte je uspořádaná osmice bitů, obvykle 2 nebo i více byteů tvoří slovo, např. u procesorů Intel řady x86 – 1 slovo = 2B = 16b.

•

Obsah paměťového místa na adrese adr bývá někdy označován ; nehrozí-li nedorozumění píše se však často adr místo .


13

Slabiková organizace paměti • •

Dva používané způsoby uložení v paměti (Big vs Little endian) Př. • 1 slabika = 1B • 1 slovo = 2B • 1 dvojité slovo = 4B [dw – Double Word] – tedy 32b • Od adresy 8001 má být uloženo dvojité slovo 1234ABCD: 1. způsob

2. způsob

Adresa

Big-endian

Little-endian

8001

12

CD

8002

34

AB

8003

AB

34

8004

CD

12


Big-endian (IBM360, Motorola 6800) Little-endian (Intel x86, DEC Alpha) Oba způsoby (Motorola 88110)

14

Zobrazení dat v paměti •

Numerická data – čísla: • V pevné řádové čárce (fixed point) • celá čísla (integer format) byte, word, … • racionální čísla (fraction format) byte, word, … • V pohyblivé řádové čárce (floating point), racionální čísla, double, float, …, matisa+charakteristika

•

Formát zobrazení: • Dvojková (binary), př. 10100011b • Šestnáctková (hexadecimal), př. A3h nebo 0xA3 • Desítková (decimal), př. 163d nebo 163 • Bez znaménka (unsigned), pouze nezáporná, byte, word, unsigned … • Se znaménkem (signed), integer, short int, signed … • Různě dlouhá, různý rozsah hodnot (short int, integer, long int, byte, word, double, …


15

Požadované vlastnosti počítače Požadované vlastnosti počítače

Required computer features •

• • • •

Řízení toku programu • synchronní akce • asynchronní akce (řízení událostmi) Přesun proměnných Zpracování proměnných Funkce vstupu/výstupu Pomocné řídicí funkce

• • • •

Program flow control • Synchronous actions • Asynchronous actions (event driven) Variable transport Variable processing Input/Output functions Auxiliary control functions

• • • •

Zabezpečení běhu Konzistence dat Ochrana proti kopírování Další …

• • • •

Operation security Data consistency Reverse engineering protection Others …

•


16

Architektura typu „von Neumann“


17

Architektura typu „Harvard“

Typ.různá šířka


18

Architektura typu „Harvard“ – další modifikace Paralelní čtení/zápis dat

Čtení konstant z Flash


19

Architektura „von Neumann“ versus „Harvard“ •

„von Neumann“

•

„Harvard“

• •

Jednodušší struktura Sdílená sběrnice – nelze paralelně transportovat instrukce a data Společný paměťový prostor instrukcí a dat. Možno pružně rozdělit paměť pro instrukce data a zásobník (pokud vše v RAM) Prostor pro zásobník (Stack) bývá dostatečný.

• •

Složitější struktura Oddělené sběrnice – možnost paralelního transportu instrukce a dat (rychlost větší) Oddělené prostory instrukcí a dat. Paměť programu (instrukcí) často širší slovo proti paměti dat – kompaktnější jednocyklové instrukční kódy. Zásobník často mimo paměť dat (rozdílná šířka paměti programu a dat). Hloubka zásobníku omezená (pak nutno přemístit do paměti dat – a to pomalé)

•

•

•

•


20

Systémová struktura počítače


21

Systémová struktura počítače Kontrolní seznam 1

Check list No.1

Počítač – sériový stroj • CPU - Procesor • Paměť programu • Paměť dat • Vstup / výstup • Společná sběrnice • Hodiny (synchronizace) • XTAL – krystal • Nulování • Periferie • Vnější paměť • Master sběrnice

Computer – sequence machine • CPU – Central Processing Unit • Program memory • Data memory • Input / output • Bus • Clock • XTAL – crystal • Reset • Peripherals • External memory • Bus master


22

Systémová struktura počítače Kontrolní seznam 2

Check list No.2

Počítač – sériový stroj • FSA - konečný automat • FSM – konečný automat • Sychronní automat • Stav automatu • Podmínky přechodu • Instrukce programu • Proměnné programu • Zásobník programu • BIOS • Operační systém • Aplikační program • Zaváděcí program

Computer – sequence machine • FSA – Finite State Automaton • FSM – Finite State Machine • Synchronous FSA • FSA state • Transition conditions • Program instructions • Program variables • Program stack • BIOS (Basic I/O System) • Operating system • Users application • Bootstrap


23

Instrukční cyklus


24

Instrukční cyklus Kontrolní seznam 3

Check list No.3

Instrukční cyklus • Čtení instrukce • Vykonání instrukce • Dekódování instrukce • Čtení operandu • Zpracování operandů • Zápis výsledku • Řídicí sběrnice (CB) • Datová sběrnice (DB) • Adresová sběrnice (AB) • Sběrnicový cyklus • Směr přenosu informace

Instruction cycle • Operational code (Opcode) fetch • Instruction execution • Instruction decode • Operand read • Operand processing • Result write • Control bus (CB) • Data bus (DB) • Address bus • Bus cycle • Information transfer direction


25

Rozdělení společné sběrnice


26

Komunikace mezi bloky Kontrolní seznam 4

Check list No.4

Komunikace mezi bloky • CB, DB, AB • Obousměrná sběrnice • Jednosměrná sběrnice • Pouze jeden bus master • Směr „čtení“ • Směr „zápis“ • Adresa platná • Data platná • Dekodér adresy • Pole paměťových jednotek • „čtení/zápis“ z/do paměti

Block communication • CB, DB, AB • Bidirectional bus • Unidirectiona bus • One bus master only • Direction „READ“ • Direction „WRITE“ • Address valid • Data valid • Address decoder • Memory array • Memory „READ/WRITE“


27

Činnost společné sběrnice (AB, DB, CB)


28

Kde číst následující instrukci

Čítač instrukcí

1) Další instrukci čti vždy z adresy uložené v PC 2) Adresa v PC se mění automaticky, po čtení instrukce ukazuje na další instrukci 3) Adresa v PC se dá změnit vykonáním instrukce skoku, cílová adresa je součástí instrukce A8B14ADP Algoritmizace a programovaní - Struktura počítače

29

Větvení programu (Jump, Branch)

Realizace větvení programu


30

Dekompozice problému na dílčí části


31

Požadavky pro volání procedury

Návratová adresa


32

Princip volání procedury (Procedure Call)

Zásobník (návratových adres)

Ukazatel zásobníku A8B14ADP Algoritmizace a programovaní - Struktura počítače

33

Synchronní akce – volání procedury Kontrolní seznam 5

Check list No.5

Synchronní akce • Čítač instrukcí - PC • Ukazatel do paměti programu • Postupné čtení • Automatická inkrementace • Vnucená adresa • Zásobník • Ukazatel zásobníku • Ukazatel na vrchol zásobníku • Vrchol zásobníku • Vlož do zásobníku - PUSH • Vyzvedni ze zásobníku - POP

Synchronous actions • Program Counter PC • Pointer to program memory • Sequential read • Auto-increment • Forced address • Stack • Stack Pointer • Pointer to stack top • TOS – top of stack • PUSH • POP


34

Synchronní akce – volání procedury - pokrač. Kontrolní seznam 6

Check list No.6

Synchronní akce - pokrač. • Začátek programu • Hlavní smyčka • Volání procedury • Návratová adresa • Začátek procedury • Tělo procedury • Bod návratu (return) • Vnořené volání • Návěští (cílová adresa skoku) • Skok (bez návratové adresy) • Hloubka zásobníku

Synchronous actions – cont'd • Program start point • Main loop • Procedure call • Return address • Procedure start • Procedure body • Return • Nested calls • Label (jump target address) • Jump (no return address) • Stack depth


35

Sdílené prostředky (sdílí je procedury)


36

Princip volání procedury (synchronní) • • • • • • • • • • • • •

Volání procedury - souhrn akcí Volání procedury je vyvolané programem (synchronní) ne vnější událostí (vnější událost – viz. přerušení) Stejným mechanismem se řídí i vnořené volání (procedura volá proceduru) Další instrukce se vždy čte z adresy právě uložené v čítači instrukcí (PC) Čti instrukci “Call“ Ulož “návratovou adresu“ (tj. obsah čítače instrukcí) do zásobníku Vlož do čítače instrukcí počáteční adresu procedury Ulož kontext do zásobníku Proveď tělo procedury Vyzvedni kontext Proveď instrukci “Return“ Ta vyzvedne “Návratovou adresu“ ze zásobníku do čítače instrukcí (PC) Pokračuj v programu za místem volání “Call“ na pozadí – tj. čti instrukci z adresy uložené v PC


37

Algoritmizace a programování

Struktura počítače KONEC

České vysoké učení technické Fakulta elektrotechnická

Algoritmizace a programování

Recommend Documents