CSC231 Homework 10 2010

--D. Thiebaut 23:57, 7 December 2010 (UTC)

---

This assignment is due on the last day of class, Tuesday 12/14 evening, at midnight.
This assignment is optional. If you submit a program for it, its grade will replace the lowest grade you have received on a previous homework assignment.

Your assignmnent

• Using compiler optimization techniques, modify the program below and make it run faster.

Finding primes less than 2,000,000

• The assembly program below tests all the integers between 2 and 2,000,000 (not included) and counts the number of primes found.

; findPrime.asm
; D. Thiebaut
;
; this program counts the number of primes number less than 1,000,000.
;
; to assemble and run:
;
; nasm  -f elf -F stabs asm_io.asm
; nasm  -f elf -F stabs findPrime.asm
; gcc -c driver.c
; gcc  asm_io.o findPrime.o driver.o  -o findPrime
; ./findPrime
;
; To measure the execution time:
;
; time ./findPrime
;
; C++ version of the program
; --------------------------
;#include<iostream>
;
;using namespace std;
;
;bool isPrime( int n );
;
;int main(){
;  int N = 2000000;
;  int count = 0;
;
;  for ( int n = 2; n < N; n++ ) 
;    if ( isPrime( n ) )
;      //cout << n << endl;
;      count++;
;
;  cout << count << endl;
;  return 0;
;}
;
;bool isPrime( int n ) {
;  for ( int i=2; i*i <= n ; i++ )
;    if ( n % i == 0 )
;      return 0;
;  
;  return 1;
;}
;
%include "asm_io.inc"


	 section	.data
N	 dd	0 		; typically set to 2,000,000
count	 dd	0		; number of primes found
n	 dd	0		; variable tested for prime property
i	 dd	0		; index of for loop

	 section	.text
	 global		asm_main

asm_main:
	mov	dword[N], 2000000 ; initialize N
	mov	dword[count], 0	  ; initialize count

;  for ( int n = 2; n < N; n++ ) 
;    if ( isPrime( n ) )
;      //cout << n << endl;
;      count++;	

       mov	dword[n], 2
forn:  mov	eax, dword[n]
       cmp	eax, dword[N]
       jge	endForn

if:    push	ax		; make room for returned value
       push	dword[n]
       call	isPrime
       pop	ax		; get returned boolean
       cmp	ax, 1
       jne	endif
       inc	dword[ count ]
endif:

       inc	dword[ n ]
       jmp	forn

endForn:
       mov	eax, [count]	; print count
       call	print_int
       call	print_nl	

       ret

;-----------------------------------------------------------------
; isPrime function.
; gets n in stack.  Returns true/false through the stack
;
;bool isPrime( int n ) {
;  for ( int i=2; i*i <= n ; i++ )
;    if ( n % i == 0 )
;      return 0;
;
;  return 1;
;}
;-----------------------------------------------------------------
isPrime:
      push	ebp
      mov	ebp, esp
      sub	esp, 4			; make room in stack for i

%define ip_ret 	word[ebp+12]
%define ip_n	dword[ebp+8]
%define ip_i	dword[ebp-4]

       mov	ip_i, 2
.for:  mov	eax, ip_i		; compare n to i*i
       mov	ebx, ip_i
       mul	ebx
       cmp	eax, ip_n
       ja	.endFor

.if:   mov	edx, 0			; divide n by i
       mov	eax, ip_n
       mov	ebx, ip_i
       div	ebx
       cmp	edx, 0			; test modulo (remainder)
       jne	.end_if
       
.ret0:
      mov	ip_ret, 0		; return 0
      mov	esp, ebp
      pop	ebp
      ret	4

.end_if:
      inc	ip_i
      jmp	.for

.endFor:
      mov	ip_ret, 1		; return 1
      mov	esp, ebp
      pop	ebp
      ret	4

• When run on grendel at 7:00 p.m., here are the execution times observed:

bash
for i in 1 2 3 4 ; do time findPrime; echo ; done

148933

real	0m4.220s
user	0m4.207s
sys	0m0.001s

148933

real	0m4.236s
user	0m4.208s
sys	0m0.002s

148933

real	0m4.272s
user	0m4.246s
sys	0m0.003s

148933

real	0m4.267s
user	0m4.207s
sys	0m0.003s

Observe that the program takes about 4.24 seconds of user time to find all the primes less than 2,000,000.

• Your assignment is to modify the assembly language program using some of the compiler optimization techniques we covered in class, and lower its user execution time.

Comparison

• The C program used as documentation in the assembly program above is shown below:

// findPrime.cpp
// D. Thiebaut
// computes the number of prime integers less than 2,000,000
// and prints out this number
//
// To compile and run:
// g++ -o findPrime2 findPrime.cpp
// ./findPrime2
//
// To compile and use as much optimization as the compiler can generate:
// g++ -O3 -o findPrim3 findPrime.cpp
// ./findPrime3
//

#include<iostream>

using namespace std;

//------------------------------------------------------
// prototypes
bool isPrime( int n );

//------------------------------------------------------
int main(){
  int N = 2000000;
  int count = 0;

  //--- test all integers less than 2,000,000 ---
  for ( int n = 2; n < N; n++ ) 
    if ( isPrime( n ) )
      //cout << n << endl;
      count++;

  cout << count << endl;
  return 0;
}

//------------------------------------------------------
// isPrime( int n )
// return true (1) if n is prime, 0 otherwise
//------------------------------------------------------
bool isPrime( int n ) {
  for ( int i=2; i*i <= n ; i++ )
    if ( n % i == 0 )
      return 0;
  
  return 1;
}

• Running the compiled and optimized version of this program on 2,000,000 integers on Grendel yields approximately 3.72 seconds, or almost half a second faster than the original assembly program.

• Your program will be graded on how close your program gets to this lower limit. For reference, I was able to get the execution time from 4.224 sec to 3.921 sec with a several optimizations. Of course documentation and presentation will also influence the grade.

Submission

• Call your program hw10.asm
• Make sure you document well all your modifications in your header and in the code.
• Submit your program as follows:

 submit hw10 hw10.asm