CSCS2650 Computer Organization

PROJECT: PRIME NUMBER COMPUTATIONS (pnc1)

OBJECTIVE

Continue 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

Add to your two separate, independent programs, one in Vircon32 C, and other in Vircon32 assembly, functionality that:

  • implements functionality for the following optimizations (both in C and assembly):
    • break: breaks from trial division/brute force when a viable factor is found (break on composite)
    • odds: assuming 2 is prime, does odds-only processing (both number and factor check)
    • sqrt: only processes up through the square root point of the number being evaluated
    • implementation here include the following:
      • break
      • odds
      • sqrt
      • break+odds
      • odds+sqrt
      • break+sqrt
      • break+odds+sqrt
  • collects the same timing data with common workloads to the brute force/naive variants from pnc0
  • new variants added to the runtime graph you made in pnc0, adjusting and re-running pnc0 variants to allow for a consistent presentation of information
    • be sure to use distinctive colors/patterns to distinguish items on the graph (again, line graph is a recommended choice)

REFERENCE

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

PNC1 C IMPLEMENTATION

PNC1/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/pnc1$ 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:

208:pnc1:final tally of results (208/208)
*:pnc1:submitted working C and assembly implementations [13/13]
*:pnc1:graph produced from timing data produced [26/26]
*:pnc1:post screenshots to class DISCORD channel [26/26]
*:pnc1:processing is correct, and to specifications [26/26]
*:pnc1:working break on composite optimization [26/26]
*:pnc1:working odds only processing optimization [26/26]
*:pnc1:working sqrt factor cap optimization [26/26]
*:pnc1:all variants and combinations thereof operational [26/26]
*:pnc1:timing data is taken out to at least 4 decimal places [13/13]

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