CSCS2650 Computer Organization

PROJECT: PRIME NUMBER COMPUTATIONS (pnc0)

OBJECTIVE

Start exploring algorithm/implementation comparison and optimization with respect to various approaches of computing prime numbers.

GRABIT

There is a GRABIT available, containing some skeleton code, an XML file, and a Makefile, that will facilitate building the cartridge.

TASK

Implement two separate, independent programs, one in Vircon32 C, and other in Vircon32 assembly, that:

  • performs a brute force/"trial-by-division" process on a range of values, 2-N
    • the values for N are some sufficient quantity still small enough to fit within an integer
    • the values for N will have some relationship (powers of 2, powers of 10/magnitudes) that ideally can be computed via some loop/equation (ie 1024, 2048, 4098, 8192, 16384, etc.)
    • the values for N have some sufficient quantity large enough where its upper set values will take some amount of time to compute (fast enough to have some relatable value, not to exceed 16 seconds)
    • for each value of N:
      • display that N/upper bound
      • tally: display the number of primes identified (2-N)
      • display the amount of time taken to do the total computation for that value of N, out to 3 decimal places
      • display each N value and result in an arrangement on the screen that can be clearly identified and read by the viewer
  • timing should go out, as reasonable, to a few decimal places, and should be consistent across all attempts.
    • timing is on the computational process only, not the display of results.
  • create a graph (using some external tool) that plots the performance of the C and assembly implementations working on identical workloads of this brute force algorithm according to the various N's and the time it took. Share your graph of your results on the class discord and on the project documentation page.
    • a line graph is the suggested best candidate
  • the assembly version is to be done entirely by hand, and make zero use of C API functions. Just the usual in/out stuff we've been doing.
  • this will not be an interactive program: it starts up, does its thing, outputs it results, then halts.
  • this brute force implementation is meant as our baseline. As such, it should not contain any optimizations or attempted improvements. As we progress through pnc1 and pnc2, this base implementation should be the least efficient. This is important, to allow us to realize the impact of various improvements we will be making in those upcoming projects.

REFERENCE

The following are reference screenshots of what your implementations should approximate:

PNC0 C IMPLEMENTATION

PNC0/C runtime

SUBMISSION

To be successful in this project, the following criteria (or their equivalent) must be met:

  • Project must be submit on time, by the deadline.
    • Late submissions will lose 33% credit per day, with the submission window closing on the 3rd day following the deadline.
  • Processing must be correct based on input given and output requested
  • Output, if applicable, must be correct based on values input
  • Code must be nicely and consistently indented and aligned
  • Code must be consistently written, to strive for readability from having a consistent style throughout
  • Code must be commented
    • Sufficient comments explaining the point of provided logic MUST be present
  • Track/version the source code in your private semester repository
  • Submit a copy of your source code to me using the submit tool by the deadline.

SUBMIT TOOL USAGE

Let's say you have completed work on the project, and are ready to submit, you would do the following (once on LAB46, with all your data present):

lab46:~/src/SEMESTER/DESIG/pnc0$ make submit

You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches.

RUBRIC

I'll be evaluating the project based on the following criteria:

156:pnc0:final tally of results (156/156)
*:pnc0:submitted working C and assembly implementations [26/26]
*:pnc0:post screenshots to class DISCORD channel [26/26]
*:pnc0:processing is correct, and to specifications [26/26]
*:pnc0:no optimizations or improvements on the process [26/26]
*:pnc0:graph produced from timing data produced [26/26]
*:pnc0:timing data is taken out to at least 3 decimal places [26/26]

ADDITIONALLY

  • Solutions not abiding by spirit of project will be subject to a 50% overall deduction
  • Solutions not utilizing descriptive why and how comments will be subject to a 25% overall deduction
  • Solutions not utilizing indentation to promote scope and clarity or otherwise maintaining consistency in code style and presentation will be subject to a 25% overall deduction
  • Solutions not organized and easy to read (assume a terminal at least 90 characters wide, 40 characters tall) are subject to a 25% overall deduction