Memory Management (interrupt Priority Approach) Report

MEMORY MANAGEMENT (INTERRUPT PRIORITY APPROACH)

2006-2007 PROJECT REPORT SUBMITTED TO THE FACULTY OF ELECTRONICS AND COMMUNICATION ENGINEERING NATIONAL INSTITUTE OF TECHNOLOGY, WARANGAL (A.P) (DEEMED UNIVERSITY) BACHELOR OF TECHNOLOGY IN ELECTRONICS AND COMMUNICATION ENGINEERING SUBMITTED BY AMIT KUMAR KARNA (04403) DEVENDER BUDHWAR (04411) DINESH KUMAR (04412)

Under the Guidance of Mr. P. Murlidhar DEPARTMENT OF ELECTRONICS AND COMMUNICATION ENGINEERING NATIONAL INSTITUTE OF TECHNOLOGY (DEEMED UNIVERSITY) WARANGAL-506004(A.P)

1

Acknowledgements

We would like to express our sincere thanks to our faculty, P. Murlidhar, Department of Electronics and Communication Engineering, National Institute of Technology, Warangal for his constant encouragement, splendid and gracious guidance throughout our work. He has been a constant source of inspiration and helped us in each stage. We express our deep gratitude to him for such encouragement and kindly cooperation.

Amit Kumar Karna (4403) Devender Budhwar (4411) Dinesh Kumar (4412)

2

CONTENTS

Abstract Introduction Priority Interrupt Algorithm VHDL Implementation The Memory Management Unit Components ™ Synchronous RAM ™ Address and Data Bus Multiplexer Conclusions References

ABSTRACT An MMU is a controller that allows a common resource memory to be shared by two or more processors depending on various input control signals. It provides the access to memory to one of the processor according to priority. Being an Interrupt service procedure, time of processor is managed efficiently. We have used the fixed priority algorithm. This approach allows a wide design exploration through automatic generation/selection of arbitration schemes.

INTRODUCTION For our EDA-II project we developed a “Memory Management Controller” where we implemented the ‘priority interrupt’ algorithm. An exclusion device is a controller that allows a common resource such as memory to be time shared by two or more processors depending on various input control signals. The purpose of this project was an implementation of one of the conventional algorithm for memory management control. We developed the algorithm, and implemented in VHDL language. The program was simulated using Altera Quartus-II. The net-list and .sof and .pof files have been obtained to dump the code onto FPGA. We chose this project because it is an ambitious project aimed to challenge us as well as provide a level of sophistication that would allow this project to be applicable not only as a semester project but to potentially be used in future projects.

1

Problem statement: Three processors are required to time share a Synchronous RAM of size 1024*16.The address bus is 10 bits wide and the data bus is 16 bits wide. There is a r/w signal which allows the processors to read data from the memory or write data into the memory. The controller is supposed to control access to the common memory depending on the request signals received by the three processors depending on the following algorithms.

Overall Goal: Memory Management Control Goal: Produce a successful realization of memory management controller. Sub Goal 1: Develop individual components Sub Goal 2: Integrate the components to form a complete module Sub Goal 3: Implement on FPGA kit We successfully reached sub goal 3 except that we did not demonstrate in hardware due to the limited time and limited number of accessible pins available on FPGA - EP1C6Q240C8 kit, we could not actually implement in hardware.

2

PRIORITY INTERRUPT ALGORITHM Each processor is assigned a priority and depending on the priority a CPU is given access. When a lower priority processor is active and the controller receives the request signal from a higher priority processor, the latter is given access until its job is finished after which the lower priority processor is given access. Nested interrupts should be allowed.

STATE DIAGRAM:

3

VHDL IMPLEMENTATION VHDL: ‰ ‰ ‰ ‰ ‰

VHSIC Hardware Definition Language. Common language for designers. High level language. Simulation synthesis and analysis tools are available. Softwares: Quartus-II/Xlinix

DESIGN Unit Names ¾ Entity ƒ Meaningful name describing the purpose of the circuit. ¾ Architecture ƒ According to the modeling style used (i.e., Behavioral, Procedural, Dataflow, or Structural) or to some specific architecture property. ¾ Configuration ƒ Name of the corresponding entity with suffix "Cfg“. ¾ Package ƒ Name of the design (i.e., top-level entity) with suffix "Pkg“. ¾ Testbench (entity, architecture, package) ƒ Name of corresponding entity with suffix "Tb“. ¾ Library (package) ƒ Library name with suffix "Lib". FPGA ‰ Benefits of using FPGA ¾ Programmed by user at their site using programming hardware. ¾ Can implement tens of thousands of gates on logic on a single IC. ¾ Can be programmed many times. ¾ Short development time. ¾ Low cost. ¾ FPGA kit in lab: EP1C6Q240C8 Hierarchy ‘n’ fpga occupancy

4

COMPONENTS:• •

Synchronous RAM Address and Data Bus Multiplexer

FPGA Occupancy:-

Project navigator

5

State Diagram Simulation:

Conditions:

6

MEMORY MANAGEMENT UNIT: PRIORITY INTERRUPT MMU: Entity: In this algorithm, A is having the highest priority among A, B and C. If B is having the access of the memory and A requests for the access, then the memory is allocated to A until A stops sending its request and is true in case of B and C also in which B is having a high priority…..!

RTL:

7

TECHNOLOGY VIEW: m u l ti p l e x:m u l t a d d A [0 ] a d d A [1 ] a d d A [2 ] a d d A [3 ] a d d A [4 ] a d d A [5 ] a d d A [6 ] a d d A [7 ] a d d A [8 ] a d d A [9 ] a d d B [0 ] a d d B [1 ] a d d B [2 ] a d d B [3 ] a d d B [4 ] a d d B [5 ] a d d B [6 ] a d d B [7 ] a d d B [8 ] a d d B [9 ] a d d C [0 ] a d d C [1 ] a d d C [2 ] a d d C [3 ] a d d C [4 ] a d d C [5 ] a d d C [6 ] a d d C [7 ] a d d C [8 ] a d d C [9 ] d a ta A [0 ] d a ta A [1 ] d a ta A [2 ] d a ta A [3 ] d a ta A [4 ] d a ta A [5 ] d a ta A [6 ] d a ta A [7 ] d a ta A [8 ] d a ta A [9 ] d a ta A[1 0 ] d a ta A[1 1 ] d a ta A[1 2 ] d a ta A[1 3 ] d a ta A[1 4 ] d a ta A[1 5 ] d a ta B [0 ] d a ta B [1 ] d a ta B [2 ] d a ta B [3 ] d a ta B [4 ] d a ta B [5 ] d a ta B [6 ] d a ta B [7 ] d a ta B [8 ] d a ta B [9 ] d a ta B [1 0 ] d a ta B [1 1 ] d a ta B [1 2 ] d a ta B [1 3 ] d a ta B [1 4 ] d a ta B [1 5 ] d a ta C [0 ] d a ta C [1 ] d a ta C [2 ] d a ta C [3 ] d a ta C [4 ] d a ta C [5 ] d a ta C [6 ] d a ta C [7 ] d a ta C [8 ] d a ta C [9 ] d a ta C [1 0 ] s ta r t rw B rw C

addA[0] addA[1] addA[2] addA[3] addA[4] addA[5] addA[6] addA[7] addA[8] addA[9] addB[0] addB[1] addB[2] addB[3] addB[4] addB[5] addB[6]

addB[8] addB[9]

data_out_mux[1]~ 689 data_out_mux[2]~ 690

data_out_mux[3]~ 691

data_out_mux[3]~ 691

data_out_mux[4]~ 692

data_out_mux[4]~ 692

addC [6] addC [7]

data_out_mux[5]~ 693

data_out_mux[5]~ 693

q _b[0]

data_out_mux[6]~ 694

data_out_mux[6]~ 694

q _b[1]

data_out_mux[7]~ 695

data_out_mux[7]~ 695

q _b[2]

data_out_mux[8]~ 696

data_out_mux[8]~ 696

q _b[3]

addC [8]

data_out_mux[9]~ 697

addC [9]

data_out_mux[10]~ 698

data_out_mux[9]~ 697

q _b[4]

data_out_mux[10]~ 698

q _b[5]

dataA[0]

data_out_mux[11]~ 699

data_out_mux[11]~ 699

q _b[6]

dataA[1]

data_out_mux[12]~ 700

data_out_mux[12]~ 700

q _b[7]

dataA[2]

data_out_mux[13]~ 701

data_out_mux[13]~ 701

data_out_mux[14]~ 702

data_out_mux[14]~ 702

q _b[9]

dataA[4]

data_out_mux[15]~ 703

data_out_mux[15]~ 703

q _b[10]

dataA[5]

M ux0~ 131

M ux0~ 131

q _b[11]

dataA[6]

M ux1~ 132

M ux1~ 132

q _b[12]

dataA[7]

M ux2~ 132

M ux2~ 132

q _b[13]

dataA[8]

M ux3~ 132

M ux3~ 132

q _b[14] q _b[15]

dataA[9]

M ux4~ 132

M ux4~ 132

dataA[10]

M ux5~ 132

M ux5~ 132

dataA[12] dataA[13] dataA[14]

M ux6~ 132 M ux7~ 132 M ux8~ 132 M ux9~ 132

dataA[15]

M ux10~ 139

dataB[0]

M ux11~ 139

dataB[1]

M ux12~ 139

dataB[2]

M ux13~ 139

dataB[3]

M ux14~ 139

dataB[4]

M ux15~ 139

dataB[5]

M ux16~ 139

dataB[6]

M ux17~ 139

dataB[7]

M ux18~ 139

M ux6~ 132 M ux7~ 132 M ux8~ 132 M ux9~ 132 rw

D AT AIN ! OE

M ux19~ 139

dataB[9]

M ux20~ 139

D AT AIN

dataB[10]

M ux21~ 139

! OE

dataB[11]

M ux22~ 139 M ux23~ 139

dataB[13]

M ux24~ 139

dataB[14]

M ux25~ 139

dataB[15]

M ux26~ 180

dataC [0]

dataC [2] dataC [3]

dataC [6]

dataC [11]

c u r r _ s ta te .s 2

D AT AA

LC ELL (AAF 0)

D AT AC

dataC [13]

C LK

c u r r _ s ta te .s 1

p e n a b le A

C OM BO U T

D AT AB C O M BO U T

D AT AD

R EG O U T

D AT AD

D AT AA

c u r r _ s ta te .s 4

SYN C H _D AT A LC ELL ( C F C 0)

co m b ~3 2 0 D AT AA D AT AB D AT AC

D AT AB

D AT AB

D AT AA D AT AB R EG O U T

D AT AC

D AT AB

C O M BO U T

LC ELL ( 3322)

D AT AA D AT AB D AT AC

D AT AD

D AT AB D AT AC

C O M BO U T

C O M BO U T

D AT AD

D AT AC

! OE

PAD O U T

d a ta _ w r _ o u t[8 ]

O U T PU T

d a ta _ w r _ o u t[7 ] D AT AIN C O M BO U T

C O M BO U T

D AT AC

d a ta _ w r _ o u t[7 ]

d a ta _ w r _ o u t[6 ] D AT AIN

rw

! OE C O M BO U T

D AT AD

LC ELL ( F E00)

PAD O U T

O U T PU T

LC ELL ( 0F 0C )

D AT AA

D AT AD

! OE

D AT AD

co m b ~3 1 5 D AT AA D AT AB

d a ta _ w r _ o u t[9 ]

d a ta _ w r _ o u t[8 ] D AT AIN

LC ELL ( 5544)

D AT AB D AT AC

LC ELL ( 1044)

LC ELL ( F F A5)

d a ta _ w r _ o u t[1 0 ]

p e n a b le C C O M BO U T

D AT AD

D AT AD

PAD O U T

O U T PU T

D AT AA

co m b ~3 1 8 D AT AA

co m b ~3 1 7 D AT AA D AT AC

d a ta _ w r _ o u t[1 1 ]

d a ta _ w r _ o u t[9 ]

D AT AB

LC ELL ( 5455)

PAD O U T

O U T PU T

penableC

! OE

p e n a b le B C O M BO U T

D AT AD

LC ELL ( F F F E)

d a ta _ w r _ o u t[1 2 ]

O U T PU T

D AT AIN ! OE

co m b ~3 1 6

LC ELL ( 0100)

R EG O U T

D AT AC

PAD O U T

d a ta _ w r _ o u t[1 0 ]

dataC [15] penableA

D AT AIN

LC ELL ( 32F F )

D AT AD

dataC [14]

d a ta _ w r _ o u t[1 3 ]

O U T PU T

penableB

D AT AD

C O M BO U T

D AT AD

D AT AC

LC ELL (0100)

C LK

! AC LR C LK D AT AA

C O M BO U T

D AT AD

! AC LR

co m b ~3 1 9

PAD O U T

d a ta _ w r _ o u t[1 1 ] D AT AIN ! OE

dataC [12]

! AC LR

co m b~3 1 3 D AT AA D AT AC

R EG O U T

d a ta _ w r _ o u t[1 4 ]

O U T PU T

dataC [7]

! AC LR

PAD O U T

d a ta _ w r _ o u t[1 2 ] D AT AIN ! OE

dataC [9]

d a ta _ w r _ o u t[1 5 ]

O U T PU T

dataC [4]

dataC [10]

PAD O U T

d a ta _ w r _ o u t[1 3 ] D AT AIN ! OE

dataC [5]

dataC [8]

PAD O U T

O U T PU T

d a ta _ w r _ o u t[1 4 ]

dataB[8]

dataB[12]

d a ta _ r d _ o u t[0 ] d a ta _ r d _ o u t[1 ] d a ta _ r d _ o u t[2 ] d a ta _ r d _ o u t[3 ] d a ta _ r d _ o u t[4 ] d a ta _ r d _ o u t[5 ] d a ta _ r d _ o u t[6 ] d a ta _ r d _ o u t[7 ] d a ta _ r d _ o u t[8 ] d a ta _ r d _ o u t[9 ] d a ta _ r d _ o u t[1 0 ] d a ta _ r d _ o u t[1 1 ] d a ta _ r d _ o u t[1 2 ] d a ta _ r d _ o u t[1 3 ] d a ta _ r d _ o u t[1 4 ] d a ta _ r d _ o u t[1 5 ]

d a ta _ w r _ o u t[1 5 ]

dataC [1]

C LK

q _b[8]

dataA[3]

dataA[11]

D AT AA

re q C

data_out_mux[0]~ 688

data_out_mux[1]~ 689 data_out_mux[2]~ 690

addC [2] addC [3] addC [4]

LC ELL ( 5050)

rw A

c lk data_out_mux[0]~ 688

addC [0] addC [1]

addC [5]

c u r r _ s ta te .s 3 re s e t c lk re q A re q B

m e m o r y:m e m

addB[7]

LC ELL ( F A0A)

PAD O U T

d a ta _ w r _ o u t[6 ]

O U T PU T

d a ta _ w r _ o u t[5 ] D AT AIN ! OE

PAD O U T

d a ta _ w r _ o u t[5 ]

O U T PU T

d a ta _ w r _ o u t[4 ]

d a ta C [1 1 ] d a ta C [1 2 ] d a ta C [1 3 ] d a ta C [1 4 ] d a ta C [1 5 ]

D AT AIN ! OE

PAD O U T

d a ta _ w r _ o u t[4 ]

O U T PU T

d a ta _ w r _ o u t[3 ] D AT AIN ! OE

PAD O U T

d a ta _ w r _ o u t[3 ]

O U T PU T

d a ta _ w r _ o u t[2 ] D AT AIN ! OE

PAD O U T

d a ta _ w r _ o u t[2 ]

O U T PU T

d a ta _ w r _ o u t[1 ] D AT AIN ! OE

PAD O U T

d a ta _ w r _ o u t[1 ]

O U T PU T

d a ta _ w r _ o u t[0 ] D AT AIN ! OE

PAD O U T

d a ta _ w r _ o u t[0 ]

O U T PU T

p r e s e n t~ 1 4 D AT AB D AT AD

C O M BO U T

p r e s e n t[2 ] D AT AIN ! OE

LC ELL ( 0033)

PAD O U T

p r e s e n t[2 ]

O U T PU T

p r e s e n t[1 ] D AT AIN ! OE

PAD O U T

p r e s e n t[1 ]

O U T PU T

p r e s e n t[0 ] D AT AIN ! OE

PAD O U T

O U T PU T

Flow Summary:

8

p r e s e n t[0 ]

Simulation results:

Fig. Simulation output of priority interrupt memory management controller

9

COMPONENTS of MMU

MEMORY:

Entity: Here we have taken 1 kb (1024 bytes) depth of 16 bit vectors. The memory is accessed by only one processor at a time which is ensured by the multiplexer used...

RTL:

10

Technology view:

Flow Summary:

11

Simulation:

MUTLIPLEXER:

ENTITY: The multiplexer selects the address bus and the data bus depending on the condition, i.e , among which of the processors ,A B or C are enabled and then it gives selects any one of the processor depending on the previous conditions and give it the excess to memory…At a time only one processors can get memory excess...

12

RTL:

Technology view:

13

Flow Summary:

Simulation:

14

VHDL CODE: VHDL code of Main Programme – PRIORITY INTERRUPT MEMORY MANAGEMENT <MAIN.VHD> library IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.STD_LOGIC_ARITH.ALL; use IEEE.STD_LOGIC_UNSIGNED.ALL; entity main is port( reqA,reqB,reqC:in std_logic; clk,reset:in std_logic; dataA,dataB,dataC:in std_logic_vector(15 downto 0); addA,addB,addC:in std_logic_vector(9 downto 0); data_rd_out:out std_logic_vector(15 downto 0); --out from memory present:out std_logic_vector(2 downto 0); data_wr_out:out std_logic_vector(15 downto 0); --out from mux rwA,rwB,rwC:in std_logic; start:in std_logic ); end main;

architecture Behavioral of main is component counter is port(req:in std_logic; enable:in std_logic; finish:out std_logic; clk:in std_logic --cnt:out integer ); end component counter; component memory is port(r_w:in std_logic ; data_in:in std_logic_vector(15 downto 0); data_out:out std_logic_vector(15 downto 0); addr_bus:in std_logic_vector(9 downto 0); clk:in std_logic ); end component memory; component multiplex is port(s:in std_logic_vector(2 downto 0); data_busA:in std_logic_vector(15 downto 0); data_busB:in std_logic_vector(15 downto 0); data_busC:in std_logic_vector(15 downto 0);

15

addr_busA:in std_logic_vector(9 downto 0); addr_busB:in std_logic_vector(9 downto 0); addr_busC:in std_logic_vector(9 downto 0); data_out_mux:out std_logic_vector(15 downto 0); addr_out_mux:out std_logic_vector(9 downto 0)); end component multiplex; signal data_out:std_logic_vector(15 downto 0); signal add_out:std_logic_vector(9 downto 0); type states is (s0,s1,s2,s3,s4); signal next_state,curr_state:states; signal ackA,ackB,ackC,nenableA,nenableB,nenableC,penableA,penableB,penab leC:std_logic :='0'; signal ll:std_logic_vector( 2 downto 0); signal rw,preqA,preqB,preqC:std_logic; begin --combine bits to form sel line for mux ll<=(penableA & penableB & penableC); mult:multiplex port map(ll,dataA,dataB,dataC,addA,addB,addC,data_out,add_out); -- data_out and add_out from mux is feed to memory -- data_rd_out is o/p from memory depending on rw signal mem:memory port map(rw,data_out,data_rd_out,add_out,clk); rr1: process(clk,reset) begin if reset='1' then curr_state <= s1; elsif( clk='1' and clk'event) then curr_state<=next_state; end if; end process rr1; control_path: process(curr_state,reqA,reqB,reqC) variable temp : std_logic_vector(2 downto 0); begin temp := (reqA & reqB & reqC); case curr_state is when s0 => present<="ZZZ"; if( start='1')then next_state<=s1; else next_state<=s0; end if; when s1 => present<="ZZZ";

16

if(temp(2)='1')then --reqA next_state<=s2; elsif(temp(1)='1')then --reqB next_state<=s3; elsif(temp(0)='1')then --reqC next_state<=s4; else next_state<=s1; end if; when s2 => present<="100"; if(( reqA='0')and temp(1)='1')then next_state<=s3; elsif(( reqA='0')and temp(0)='1')then next_state<=s4; elsif temp="000" then next_state<=s1; else next_state<=s2; end if; when s3 => present<="010"; if(reqA='1') then next_state <= s2; elsif((reqB='0')and temp(0)='1')then next_state<=s4; elsif temp="000" then next_state<=s1; else next_state<=s3; end if; when s4=> present<="001"; if(reqA='1') then next_state <= s2; elsif (reqB ='1' and reqA = '0') then next_state <= s3; elsif temp="000" then next_state<=s1; else next_state<=s4; end if; end case; end process control_path; data_path:process(curr_state,rwA,rwB,rwC,data_out) begin if(curr_state=s1)then penableA<='0'; penableB<='0'; penableC<='0'; elsif(curr_state=s2)then

17

penableA<='1'; penableB<='0'; penableC<='0'; rw<=rwA; elsif(curr_state=s3)then penableA<='0'; penableB<='1'; penableC<='0'; rw<=rwB; elsif(curr_state=s4)then penableA<='0'; penableB<='0'; penableC<='1'; rw<=rwC; end if; data_wr_out<=data_out; end process data_path; end Behavioral; VHDL code of MEMORY: <MEMORY.VHD>

library IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.STD_LOGIC_ARITH.ALL; use IEEE.STD_LOGIC_UNSIGNED.ALL; entity memory is port(r_w:in std_logic ; data_in:in std_logic_vector(15 downto 0); data_out:out std_logic_vector(15 downto 0); addr_bus:in std_logic_vector(9 downto 0); clk:in std_logic); end memory; architecture Behavioral of memory is type mem is array (2**10-1 downto 0) of std_logic_vector (15 downto 0); --signal ram_output:std_logic_vector(15 downto 0); signal RAM : mem:=(others=>(others=>'0')); begin p1: process(clk,r_w) begin if(clk'event and clk='1')then if(r_w='1') then --read from address data_out<=RAM(conv_integer(addr_bus)); elsif(r_w='0')then RAM(conv_integer(addr_bus))<=data_in; -write at given address

18

end if; end if; end process p1; end Behavioral;

VHDL CODE of MUNLTIPLEXER: <MULTIPLEX.VHD> library IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.STD_LOGIC_ARITH.ALL; use IEEE.STD_LOGIC_UNSIGNED.ALL; entity multiplex is port(s:in std_logic_vector(2 downto 0); data_busA:in std_logic_vector(15 downto 0); data_busB:in std_logic_vector(15 downto 0); data_busC:in std_logic_vector(15 downto 0); addr_busA:in std_logic_vector(9 downto 0); addr_busB:in std_logic_vector(9 downto 0); addr_busC:in std_logic_vector(9 downto 0); data_out_mux:out std_logic_vector(15 downto 0); addr_out_mux:out std_logic_vector(9 downto 0)); end multiplex; architecture Behavioral of multiplex is begin with s select data_out_mux <= data_busA when "100", data_busB when "010", data_busC when "001", (others=>'Z') when others; with s select addr_out_mux <= addr_busA when "100", addr_busB when "010", addr_busC when "001", (others=>'Z') when others; end Behavioral;

19

CONCLUSIONS I. Memory can be simultaneously serviced to multi processes. II. Being an Interrupt service procedure, time of processor is managed efficiently. III. FPGA/VHDL combination is a very powerful design tool. -- Versatile, Adaptable, Efficient, Economic IV. The given algorithm can be used to implement process scheduling.

References 1. A VHDL Primer, 3rd edition : J. Bhasker 2. Computer Organization and Architecture: William Stallings

20