CHAPTER NUMBER TITLE PAGE NUMBER

1 8086 MICRO 1
PROCESSOR
OVERWIEW

2 INTRODUCTION 9

3 BINARY SEARCH 16

4 DEVELOP AND
EXECUTE ALP THAT
IMPLEMENTS
BINARY SEARCH
ALGORITHM USING
EMU806

5 CONCLUSION 19
DEVELOP AND EXECUTE ALP THAT IMPLEMENTS BINARY SEARCH ALGORITHM USING EMU806

8086 Microprocessor Overview:

The Intel 8086 is a 16-bit microprocessor developed by Intel and introduced in 1978. It was
designed for general-purpose computing and became the basis for the x86 architecture,
which has been used in modern computer systems. It is an important processor in the
history of computing due to its architecture and design principles, which influenced the
development of personal computers (PCs).
The 8086 operates in real mode and can access up to 1 MB of memory through segmented
memory addressing. It supports 16-bit data handling, and the instruction set architecture
(ISA) is rich with arithmetic, logic, control, and data manipulation instructions.

1. Key Features of Intel 8086

1. 16-bit Microprocessor:
o The 8086 is a 16-bit microprocessor, meaning its data bus is 16 bits wide. It
can process 16 bits of data in a single operation, which allows for more
efficient handling of data than 8-bit processors.
2. 20-bit Address Bus:
o The processor has a 20-bit address bus, allowing it to address up to 1 MB of
memory (2^20 = 1,048,576 bytes). The address space is calculated as:
Address Space=2Address Bus Width=220=1 MB\text{Address Space} = 2^{\
text{Address Bus Width}} = 2^{20} = 1 \
text{ MB}Address Space=2Address Bus Width=220=1 MB
3. Pipelining:
o The 8086 uses a primitive form of instruction pipelining, where the Bus
Interface Unit (BIU) fetches instructions in advance and stores them in a 6-
byte prefetch queue. While one instruction is being executed, the next
instruction is fetched from memory, which increases the overall processing
speed.
4. Segmented Memory Architecture:
o The 8086 divides its memory into segments, allowing it to address 1 MB of
memory using 16-bit registers for each segment and an offset value. The four
main memory segments are:
 Code Segment (CS): For storing program instructions.
  Data Segment (DS): For storing data.
 Stack Segment (SS): For managing the stack.
 Extra Segment (ES): Used for additional data or string operations.
5. Multiplication/Division Instructions:
o The 8086 supports hardware-based multiplication and division instructions,
unlike its predecessors (e.g., 8080, 8085), which required software routines
for such operations.
6. 16-bit General Purpose Registers:
o The processor has eight general-purpose registers (AX, BX, CX, DX, SI, DI, BP,
SP) that can store data and addresses. The registers can be divided into 8-bit
halves for handling 8-bit data.
7. Clock Speed:
o The 8086 operates at clock speeds of 5 MHz, 8 MHz, or 10 MHz, depending
on the specific version and configuration.
8. Interrupt Handling:
o The 8086 provides robust support for hardware and software interrupts,
including maskable and non-maskable interrupts. It has 256 possible interrupt
types, supporting both vectored and non-vectored interrupts.
9. Dual Modes of Operation:
o Minimum Mode: In this mode, the 8086 functions as a standalone processor.
It generates all necessary control signals for memory and I/O operations.
o Maximum Mode: In this mode, the 8086 is used in multi-processor systems
(coordinated with a coprocessor like the 8087 math coprocessor). Control
signals are generated externally using the 8288 bus controller.
10. External Bus Controller (8288):
o In maximum mode, the 8288 Bus Controller is used to control the external
bus. It works in conjunction with other processors and handles the sharing of
resources among them.
11. Support for Coprocessors:
o The 8086 can be paired with additional processors like the 8087 numeric
coprocessor for handling floating-point arithmetic operations, improving the
processor's computation power.
12. Flexible Instruction Set:
o The 8086 has a powerful and flexible instruction set, with support for:
  Arithmetic operations (ADD, SUB, MUL, DIV).
 Logical operations (AND, OR, XOR).
 Control flow instructions (JMP, CALL, RET).
 Data transfer instructions (MOV, PUSH, POP).
 String manipulation instructions (MOVS, CMPS, SCAS).
 Bit manipulation instructions.

2. Block Diagram of 8086 Microprocessor

The Intel 8086 microprocessor consists of two major components:
 Bus Interface Unit (BIU)
 Execution Unit (EU)
a) Bus Interface Unit (BIU)
The Bus Interface Unit (BIU) is responsible for interfacing the microprocessor with memory
and I/O. It handles all communication with the outside world, including the prefetching of
instructions from memory, managing the instruction queue, and calculating physical
addresses.
Components of BIU:
 Instruction Queue: The BIU fetches instructions from memory and stores them in the
6-byte instruction queue. This enables pipelining, where instructions can be fetched
while the previous instruction is still being executed.
 Segment Registers: These store base addresses of different segments in memory:
o Code Segment (CS): Points to the base of the code segment.
o Data Segment (DS): Points to the base of the data segment.
o Stack Segment (SS): Points to the base of the stack segment.
o Extra Segment (ES): Used for additional memory access.
 Instruction Pointer (IP): Points to the next instruction to be executed. This, combined
with the CS, helps in determining the address of the next instruction.
b) Execution Unit (EU)
The Execution Unit (EU) is responsible for executing the instructions fetched by the BIU. It
decodes instructions, performs arithmetic and logical operations, and controls the flow of
program execution.
Components of EU:
 General-Purpose Registers:
o AX: Accumulator (used in arithmetic operations).
o BX: Base register (used in addressing modes).
o CX: Count register (used in loops and shifts).
o DX: Data register (used in multiplication and division).
 Index Registers:
o SI (Source Index): Used for indexed addressing and string operations.
o DI (Destination Index): Used for string operations and memory access.
 Pointer Registers:
o SP (Stack Pointer): Points to the top of the stack.
o BP (Base Pointer): Used to access parameters passed in the stack during
function calls.
 Flags Register: This register contains condition flags that indicate the result of
operations. Important flags include:
o Carry Flag (CF): Set if there is a carry out or borrow in arithmetic operations.
o Zero Flag (ZF): Set if the result of an operation is zero.
o Sign Flag (SF): Set if the result of an operation is negative.
o Overflow Flag (OF): Set if signed arithmetic operations overflow the capacity
of the register.
3. Memory Segmentation in 8086:
The 8086 uses segmented memory addressing, where memory is divided into segments. Each
segment can be up to 64 KB in size. There are four types of segments:

 Code Segment (CS): Stores the executable instructions of the program.

 Data Segment (DS): Stores global and static variables and data.

 Stack Segment (SS): Stores function call return addresses, local variables, and the stack.

 Extra Segment (ES): Used in string operations and additional data storage.

Calculating Physical Address in 8086:

The 8086 uses 20-bit physical addresses, even though the segment and offset values are both 16 bits
wide. The physical address is calculated as:

Physical Address=(Segment Value×16)+Offset Value\text{Physical Address} = \text{(Segment Value} \

times 16) + \text{Offset Value}Physical Address=(Segment Value×16)+Offset Value

For example:

 CS = 1234H, IP = 5678H
 would result in the following physical address:
 Physical Address = (1234H×10H) + 5678H= 12340H + 5678H = 179B8H
4. Registers of the 8086 Microprocessor:
The 8086 microprocessor has a total of 14 registers, each 16 bits wide. These registers can
be classified into various categories:
a) General Purpose Registers:
1. AX (Accumulator): Primarily used in arithmetic operations.
2. BX (Base): Used in addressing modes.
3. CX (Count): Used in loops and shift operations.
4. DX (Data): Used in I/O operations and multiplication/division.
These registers can also be split into 8-bit registers:
 AX → AH (high byte), AL (low byte)
 BX → BH, BL
 CX → CH, CL
 DX → DH, DL
b) Segment Registers:
1. CS (Code Segment): Points to the segment containing the code.
2. DS (Data Segment): Points to the segment containing the data.
3. SS (Stack Segment): Points to the segment containing the stack.
4. ES (Extra Segment): Used for string and data operations.
c) Pointer and Index Registers:
1. SP (Stack Pointer): Points to the top of the stack.
2. BP (Base Pointer): Used to reference function parameters passed on the stack.
3. SI (Source Index): Used for indexed addressing and string operations.
4. DI (Destination Index): Used for string operations.
d) Special Purpose Registers:
1. IP (Instruction Pointer): Points to the next instruction to be executed.
2. Flags Register: Holds various flags that indicate the status of operations.
5. Instruction Set of 8086:
The 8086 instruction set is versatile and includes the following categories of instructions:
a) Data Transfer Instructions:
 MOV: Transfer data between registers, memory, and I/O ports.
 PUSH/POP: Push data onto the stack or pop it off.
 IN/OUT: Transfer data to/from I/O ports.
b) Arithmetic Instructions:
 ADD/SUB: Add or subtract data.
 MUL/DIV: Perform multiplication or division.
 INC/DEC: Increment or decrement the value in a register.
c) Logical Instructions:
 AND, OR, XOR: Perform bitwise logical operations.
 NOT: Perform a bitwise NOT operation.
 TEST: Test bits in a register.
d) Control Flow Instructions:
 JMP: Jump to another location in the program.
 CALL/RET: Call and return from subroutines.
 LOOP: Repeat a block of code a specified number of times.
e) String Manipulation Instructions:
 MOVS: Move strings of data from source to destination.
 CMPS: Compare strings of data.
 SCAS: Scan a string for a particular value.
f) Flag Control Instructions:
 STC/CLC: Set or clear the carry flag.
 STD/CLD: Set or clear the direction flag for string operations.

6. Applications of Intel 8086:

The 8086 microprocessor was widely used in early personal computers (PCs), including the
IBM PC, which was the first widely adopted personal computer. It also found applications in:
  Embedded systems.
 Control systems.
 Military and industrial applications.

Due to its influence, the 8086 architecture laid the groundwork for the future development of Intel’s
x86 line, which powers most personal computers today.

Modes of Operation:
The 8086 operates in real mode, where it can address up to 1 MB of memory
using segment and offset addressing.
Interrupts in 8086
The 8086 supports a mechanism called interrupts to handle external and
internal events. When an interrupt occurs, the current execution is paused, and
the processor jumps to a predefined location to execute an interrupt handler.
There are two types of interrupts:
 Hardware Interrupts: Generated by external devices.
 Software Interrupts: Generated by the program using the INT
instruction.

Advantages of the 8086 Microprocessor

1. Widespread use: The 8086’s architecture became the foundation for the x86
family of processors, which are still in use today.
2. 16-bit processing: Allows more efficient processing of data compared to older
8-bit processors.
3. Segmented memory: Offers more flexible memory management.
4. Rich instruction set: Provides powerful operations for arithmetic, logic, and
data manipulation.

Applications:
 Used in early personal computers like the IBM PC.
INTRODUCTION:
The Assembly Language Program (ALP) is a low-level code written in assembly language for a specific
CPU architecture. In this case, we are working with the Intel 8086 architecture and using the
EMU8086 emulator to implement the binary search algorithm. Let’s walk through the components
of the program in detail.

Overview of Binary Search

The binary search algorithm operates on a sorted array and works by repeatedly dividing the search
interval in half. If the value of the target is less than the middle element of the array, the search
continues in the lower half. If the value of the target is greater, the search continues in the upper
half. This process repeats until the target element is found or the search space is exhausted
(indicating that the target is not in the array).

Detailed Components of the Assembly Program

1. Segment Definitions
The 8086 processor organizes memory into segments, which are logical divisions for different types
of data and instructions. We define segments for data (where the array and variables are stored) and
code (where the instructions are written).

EXAMPLE:
ORG 100H ; Start the program at memory location 100H (for COM programs)

 ORG 100H: This directive sets the starting address for the code to 100H, which is necessary
for COM programs. COM files are loaded at offset 100H by default, so the code execution
begins at this location.

2. Data Segment
The data segment is used to define the array of sorted elements that we want to search and other
variables like the target value and result storage.

EXAMPLE:
DATA SEGMENT

array DB 10, 20, 30, 40, 50, 60, 70, 80, 90 ; Sorted array of 9 elements

target DB 50 ; Target number we are searching for

result DB ? ; Placeholder to store the result (index or not found)

DATA ENDS

 array DB ...: This defines a sorted array of 9 elements (each element is a byte, denoted by
DB). These values are hardcoded for demonstration.
  target DB 50: The target is the number we are searching for. In this case, the number is 50.

 result DB ?: This variable is used to store the index of the target if it’s found or indicate that
the target wasn’t found.

3. Code Segment
The code segment contains the instructions that will implement the binary search algorithm. It is
where the logic of the program resides.

EXAMPLE:
CODE SEGMENT

ASSUME CS:CODE, DS:DATA

 ASSUME CS:CODE, DS:DATA: This tells the assembler that the Code Segment (CS) register
points to the CODE segment and the Data Segment (DS) register points to the DATA
segment.

4. Initialization
Before we start the binary search, we need to initialize the data segment. This sets the appropriate
segment registers for accessing data.

EXAMPLE:
START:

MOV AX, DATA ; Load the address of the data segment into AX

MOV DS, AX ; Move the data segment address into DS (to access the array)

 MOV AX, DATA: The base address of the DATA segment is loaded into AX.

 MOV DS, AX: The DS register is initialized with the value in AX, so we can use DS to access
data from the DATA segment.

5. Binary Search Algorithm

The core logic of binary search is implemented in the following steps:

 Low and High Pointers: We use the SI (Source Index) register as the low pointer (starting
index) and CX (Counter) as the high pointer (last index of the array).

EXAMPLE:
MOV SI, 0 ; SI will be used as 'low' (initially 0)

MOV CX, 8 ; CX will be used as 'high' (array size - 1 = 8)

MOV DL, target ; DL contains the target value

  MOV SI, 0: Set the low pointer (starting index) to 0 (first element).

 MOV CX, 8: Set the high pointer to 8 (last element index for a 9-element array).

 MOV DL, target: Load the target value into DL for comparison.

 Main Loop: The binary search loop starts by comparing low and high. If low exceeds high, the
search terminates with the target not found.

EXAMPLE:
BINARY_SEARCH:

CMP SI, CX ; Compare low and high

JG NOT_FOUND ; If low > high, jump to NOT_FOUND (target not present)

 CMP SI, CX: Compare the values of low (SI) and high (CX).

 JG NOT_FOUND: If low is greater than high, it means the element is not in the array, and the
program jumps to the NOT_FOUND label.

 Calculate the Midpoint: The midpoint is calculated as (low + high) / 2, and this is used to
access the middle element of the array.

EXAMPLE:
MOV BX, SI ; Move low (SI) into BX
ADD BX, CX ; BX = low + high
SHR BX, 1 ;Divide by 2 (shift right)
 MOV BX, SI: Load the value of low (SI) into BX.

 ADD BX, CX: Add high (CX) to low (BX).

 SHR BX, 1: Divide the sum by 2 using the shift right (SHR) operation to get the midpoint
index.

 Compare the Target with the Midpoint Element: We load the midpoint element from the
array and compare it with the target value.

EXAMPLE:
MOV AL, array[BX] ; Load middle element into AL

CMP AL, DL ; Compare middle element with target

JE FOUND ; If equal, jump to FOUND

 MOV AL, array[BX]: Load the value of the array at the midpoint index into AL.

 CMP AL, DL: Compare the midpoint element (AL) with the target (DL).
  JE FOUND: If the values are equal, the program jumps to the FOUND label, indicating that the
target is found.

 Adjust Search Space: If the target is greater than the midpoint element, adjust the low
pointer. If the target is smaller, adjust the high pointer.

EXAMPLE:
JCMP AL, DL ; Compare the values

JB RIGHT_SEARCH ; If the target is greater, search the right half

LEFT_SEARCH:

MOV CX, BX ; Set high = mid - 1

JMP BINARY_SEARCH

RIGHT_SEARCH:

MOV SI, BX ; Set low = mid + 1

JMP BINARY_SEARCH

 Left Search (if target is smaller):

o MOV CX, BX: Set high to mid - 1.

o JMP BINARY_SEARCH: Loop back to the beginning to continue the search.

 Right Search (if target is larger):

o MOV SI, BX: Set low to mid + 1.

o JMP BINARY_SEARCH: Loop back to continue the search in the right half.

6. Target Found and Not Found Labels

If the target is found or not, the program terminates by jumping to the appropriate labels:

EXAMPLE:
FOUND:

MOV result, BX ; Store the index of the found target in result

HLT ; Halt the program

NOT_FOUND:

MOV result, FFH ; Indicate that the target was not found (FF is -1)

HLT ; Halt the program

  FOUND: If the target is found, the index is stored in result, and the program halts.

 NOT_FOUND: If the target is not found, FFH (hexadecimal for -1) is stored in result, indicating
failure, and the program halts.

7. End of Program
Finally, we declare the end of the program.

EXAMPLE:
CODE ENDS
END START
 CODE ENDS: Marks the end of the code segment.

 END START: Tells the assembler to end the program, starting at the START label
BINARY SEARCH:
The binary search algorithm is an efficient method for searching a target element in
a sorted array. It operates by repeatedly dividing the search interval in half. In
assembly language for the 8086 microprocessor, binary search follows a similar
approach, leveraging registers to store the bounds of the search space and iterating
until the target is found or the search space is exhausted.
Concept of Binary Search
 Input: A sorted array and a target element.
 Output: The index of the target element if found, otherwise a value indicating
that the target was not found (commonly -1).
Binary Search starts by comparing the middle element of the array with the target
element. Depending on the comparison, it reduces the search range:
 If the middle element matches the target, the search ends successfully.
 If the middle element is smaller than the target, it searches in the right half of
the array.
 If the middle element is larger than the target, it searches in the left half.
The process repeats, halving the array each time, until the target is found or the
search bounds overlap, indicating the target is not present in the array.

Binary Search Algorithm (Step-by-Step)

The binary search in assembly language follows a clear and structured process. Below
are the steps:
1. Initialization:
o Set BX = 0 (low index).
o Set CX = N-1 (high index), where N is the total number of elements in
the array.
o Load the target value to search into DL.
2. Calculate Middle Index:
o Compute the middle index mid = (low + high) / 2. In assembly, this is
done using:
 Add BX (low) and CX (high).
  Shift the result right by 1 (SHR) to divide by 2.
3. Compare the Middle Element with Target:
o Load the middle element from the array into AL.
o Compare the middle element with the target value stored in DL using
CMP AL, DL.
o If the values are equal (JE instruction), the target is found, and the
search ends.
o If the middle element is smaller than the target (JL), search the right
half by updating BX = mid + 1.
o If the middle element is larger than the target (JG), search the left half
by updating CX = mid - 1.
4. Update Search Bounds:
o Adjust the BX or CX registers depending on whether the target is larger
or smaller than the middle element.
o Repeat the process until BX (low index) exceeds CX (high index), which
indicates the target is not in the array.
5. Termination:
o If the target is found, the program returns the index in AX or stores it in
memory.
o If the search bounds overlap, return -1 to indicate the target is not
found.

Key Features of Binary Search in 8086:

1. Efficiency: The binary search algorithm has a time complexity of O(log n),
making it efficient for large sorted datasets.
2. Assembly Language Constructs: The program uses basic assembly language
constructs like registers, loops, and conditional jumps to implement the search
logic.
3. Memory Access: Array elements are accessed directly from memory using
offsets (e.g., ARRAY[SI]), which is characteristic of low-level programming.
4. Flag Usage: The status flags (ZF, SF, CF) are affected by CMP operations,
allowing for efficient flow control using jump instructions (JE, JL).
 DEVELOP AND EXECUTE ALP THAT IMPLEMENTS
BINARY SEARCH ALGORITHM USING EMU806

;Develop and execute ALP that implements Binary search algorithm. The data
;consists of sorted 16 bit unsigned integers. The search key is also a 16 bit
unsigned
;integer.

DATA SEGMENT
ARR DW 05H,0111H,2161H,4541H,7161H,8231H
SR EQU 4541H
MSG1 DB 'ELEMENT FOUND AT '
RES DB ' RD POSITION','$'
MSG2 DB 'ELEMENT NOT FOUND','$'
DATA ENDS

ASSUME CS:CODE,DS:DATA

CODE SEGMENT
START: MOV AX,DATA
MOV DS,AX
MOV BX,00H
MOV CX,SR
MOV DX,05H

LP: CMP BX,DX

JA FAILURE
MOV AX,BX
 ADD AX,DX
SHR AX,01
MOV SI,AX
ADD SI,SI
CMP CX,ARR[SI]
JAE BIGGER
DEC AX
MOV DX,AX
JMP LP

BIGGER: JE SUCCESS
INC AX
MOV BX,AX
JMP LP

SUCCESS:ADD AL,01H
ADD AL,2FH
MOV RES,AL
LEA DX,MSG1
JMP DISPLAY

FAILURE: LEA DX,MSG2

DISPLAY: MOV AH,09H
INT 21H
MOV AH,4CH
INT 21H

CODE ENDS
END START
EXPLANATION OF THE PROGRAM:
 ARR: A sorted array containing 6 elements, each a 16-bit unsigned integer.

 SR: The search key to look for in the array. In this case, it's set to 4541H.

 MSG1 and MSG2: Strings that will be displayed on success or failure, respectively.

 RES: Holds the result, which will be the position where the element is found.

Summary of Key Operations:

1. Binary Search:

o The program compares the search key with the middle element of the current search
bounds.

o If the search key matches the middle element, the position is stored, and a success
message is displayed.

o If the search key is smaller or larger, the bounds are adjusted, and the search
continues in the relevant half of the array.

2. Handling Success and Failure:

o When the element is found, its position is stored, and a success message is displayed
with the result.

o If the search completes without finding the element, a failure message is displayed.

Execution Process:

1. Run the Program in an emulator like EMU8086.

2. Enter Search Key: The program will search for the key 4541H in the sorted array ARR.

3. Output:

o If found, the message "ELEMENT FOUND AT X RD POSITION" will be displayed, where

X is the position.

o If not found, the message "ELEMENT NOT FOUND" will be displayed.

This is how the binary search algorithm is implemented in Assembly Language for 16-bit unsigned
integers using EMU8086.
 ABSTRACT
The Intel 8086 microprocessor, introduced in 1978, marked a significant
advancement in computer architecture. As a 16-bit microprocessor, it was capable of
addressing up to 1 MB of memory through its unique segmented memory model,
which divides memory into segments (code, data, stack, and extra). This
segmentation allows programs to utilize memory more efficiently and simplifies the
management of large codebases.
The 8086 features a comprehensive instruction set that supports arithmetic, logical,
and control flow operations, enabling complex computations and robust
programming capabilities. It operates with a maximum clock speed of 10 MHz and
employs a multiprocessing architecture, which allows multiple processors to operate
concurrently, thereby enhancing computational power and efficiency.
In a Multiprocessor Computer (MPMC) system, multiple processors work together to
execute tasks. Here, efficient data retrieval algorithms, such as binary search, play a
crucial role. The binary search algorithm operates on sorted arrays, significantly
reducing search time by repeatedly dividing the search interval in half. This results in
a time complexity of O(log n), making it much faster than linear search methods
(O(n)).
When integrating binary search into MPMC systems using the 8086 architecture,
multiple processors can concurrently handle different segments of data, thereby
expediting the search process. For example, one processor could manage the initial
array partitioning while others perform the search within their assigned segments.
This parallel processing capability optimizes resource utilization and minimizes overall
search time.
The collaboration between the 8086 microprocessor's architecture and the binary
search algorithm exemplifies the synergy of hardware and software. The 8086's
ability to support multiprocessing enhances the performance of data-intensive
applications, while the efficiency of binary search allows for rapid data retrieval,
crucial in environments requiring high performance and scalability.
In summary, the Intel 8086 microprocessor, with its advanced architecture and
multiprocessing capabilities, paired with efficient algorithms like binary search,
illustrates a pivotal moment in computing history. This combination not only
facilitated the evolution of personal computing but also laid the groundwork for
future developments in processor technology and algorithmic efficiency, both of
which remain relevant in today's computational landscape.