AHHHHHHHHHHHH


we solved it! :D

Updates...this is crunch time!

Updates:

-from Erick: his counter is golden...(we'll see how golden it is when it has to talk to Andrew's crazy HW)
-from me: uart works for everything, but we're commenting that out for now...so Andrew can test his HW faster (hahaha...my computer can't take it anymoreeee)
-from Vlad: "no new code unfortunately.it's all in your (referring to everyone else) hands now"
-from Andrew: (bear w/ me...this is gonna be a long one)
Now for the update:
It doesn't work. But! :) We're now reading SRAM correctly, and we have a
debug register that gives us some insight into what is happening. It
actually took us most of the day to figure out if SRAM was broken and
then how to fix it, but we're sure it is fixed now, and that the
data_available signal is propagating through our system at the rate I
expect.

What remains to be fixed:

o Timing; particularly when the numberColumnRegisters see new data wrt
the cell counter. This will take until lunch tomorrow. But fixing this
will mean "it works."

o The 'done' signal needs to be fixed up to be a function of both the
cell counter and the data_available signal (Right now we announce done
when the cellcounter is 1111; but this doesn't give time to read the
16th cell from memory! This is why I tell Aliaa it only works for N=3
atm. It is a simple fix, but needs to wait until after timing is fixed.

o For performance, I want to send the 'clear' and 'go' bits at the same
time to reduce overhead. This basically means throwing the go signal in
a pipe. Trivial.

o The checksum_routines need to be amended so that setting 'N2' is only
done once. Trivial.

o Once all that is done and one possibility row is working fast (--side note by Aliaa: WHAT! FAST! what a concept!), we'll
put in Erick's awesome counter to get the other modes. Probably not too
bad.

o I think it is doable to do all that Monday. Tuesday I can try to add a
controller so we can just be called once per method, rather than once
for every row/column/block.

----he couldn't log in for some reason and requested to have this update posted. ----

dinner time...all day in lab again tomorrow.

Good extension or bad extension???

we're slowly inching towards hw-sw integration....and i have yet to figure out how uart really works. might try what happens with the hyperterminal....tomorrow!

As for the guys, Vlad is working on something...maybe his part of the report? Meanwhile...Andrew is working on loads of HW stuff. Erick has been compiling stuff for me! yayy :) he's yet to mess around with the given c-code & verilog, though, to see if the addressing all works out.

ttl: how long?? that extension was a double-edged sword...(Who wants to be in kemper the day we have our ceremony??)

Our Runtimes

we have started a scoreboard on the whiteboard in class...mainly, it's Infinite Execution vs BNSS vs us, and we welcome (i guess?) all the other teams too (your names are all up on there at least for the next 2 hours!).

Here are our runtimes:

Puzzle Runtime
3_1 11.31854 milliseconds
3_2 12.76578 milliseconds
4_1 0.90984202 seconds
4_2 8.55818944 seconds
5_1 2.198 seconds
5_2 FAIL (SLOW)
6_1 FAIL (SLOW)
6_2 2.25446164 seconds
7_1 9.26728258 seconds
7_2 FAIL (SLOW)
8_1 FAIL (puzzle is MESSED UP)
8_2 1.57 seconds
9_1 FAIL (SLOW)
9_2 12.3104381 seconds
10_1 ~4 minutes
10_2 26.23 second

For most updated times, click here

Long march to Friday's Demo

Over the weekend I finished most of the hardware accelerator logic, (Erick is doing the rest), and Vlad modified the software to use bit vectors rather than an array. Now it is time to figure out the details of interfacing with memory. We can use the CRC checksum accelerator as an example.. but it has more features than we need. For instance, it would be okay for the CPU to stall while waiting for the accelerator, rather than doing other work while waiting for an interrupt. Supporting these additional features will make the design more complicated; on the otherhand, trying to make something from scratch will almost certainly take longer to figure out.

Aliaa is working on the serial interface and trying to run the current software on the NIOS w/ SRAM. Vlad is improving his bit vector code to remove division where possible.

I'm not sure that we will really make the Friday deadline for full integration; but Sunday would be doable.

hard puzzles:
5_2
6_1
7_2
9_1
10_1

dunno what's wrong with 8_1. NOTE: there was a missing comma in 6_1, but I fixed that. hopefully the t.a remembers...line 31, the comma between 0 & 11 for puzzle 6_1 (this wasn't fixed even in the latest version of puzzles).

all other puzzles were solved pretty quickly on linux :) now to figure out that RS232 cable...

haven't figured out interfacing SRAM with checksum accelerator...pipelining reads is a little tricky, i guess. :p

We're making progress! YAY! :)

but some of those puzzles are hard (or incorrect)....boo.

Time Constraints based on Complexity of Puzzle

Tmax = 3 * 10^-4 * N^6 seconds

   N         Maximum Time Allowed

   3                  0.21 secs

   4                  1.23 secs

   5                  4.69 secs

   6                13.99 secs

   7                35.29 secs

   8                78.64 secs =    1.31 mins  (1 min and 18.64 secs)

   9              159.43 secs =  2.657 mins (2 mins and 39.43 secs)

  10                 300 secs =      5 mins

  11             531.46 secs =  8.857 mins (8 mins and 51.46 secs)

Time for a redesign

So for N=7, it takes our algorithm more than 8 hours to solve on a Pentium 4. We have analyzed how our solver is solving the puzzle; the problem it is guessing too much. While our logical methods are fast, we are spending at least 99.9% of the time using them on a puzzle that is going to be shown to be invalid.

So we need to implement more logical "human" methods. However, we have exhausted the analytic methods that operate on the data structures we store (we store the possibilities for the rows, columns, and boxes--but not the possibilities for each cell.) The more complex methods will require that we store the possibilities for every cell on the grid. So we will basically have to start over on our algorithm.

In other news, the hardware I designed for accelerating FindUniqueRow doesn't fit on the FPGA. Oops. So I'm starting over resigned to reading in only a limited number of the constraint arrays at a time and doing some processing--and also only store an even more limited amount of interim work.

As long as we are redesigning the algorithm, I think Vlad is going to aim for having the software operate on bit vectors rather than character arrays. This means we are basically throwing out our software and starting over.

Sudoku is hard.

Bump on the Road: Hardware vs. Software

With higher complexity puzzles (N>5), our software-based algorithm does not seem to solve the puzzles efficiently. We may need to implement some of our algorithm at the hardware-level with customized logic modules and see what happens when we try to solve the higher complexity puzzles; or we may need to reevaluate our software algorithm and develop further our methods to solve the sudoku puzzles. As a team, we will need to investigate and hopefully upgrade/adapt our current algorithm to solve puzzles with higher complexities faster (especially for N>5).

We are somewhat re-thinking our hardware design so as to not take up as many wires. We've been running the N=6 and N=7 puzzles to no avail, so that is also a problem.

More updates later.

Eventful Friday, Apr 24th

We didn't quite get to run the N=11 puzzle (since we didn't find one). I found a puzzle with N=10, but we haven't parsed the file yet.

We were instead trying to figure out the necessary memory components. In doing so, we successfully ran the existing software-only version completely from on-chip memory, for N=3.

On Monday, we plan to work more with the memory components, now that the SRAM tutorial is up. I am also hoping we get to drawing a more detailed block diagram for the hardware components, taking our lessons from EEC 183.

Midterms are coming up though...:(

First post!

A rough outline of our design plan can be found here.

1st post! At this point, we have our software implementation up and running. We plan to test an N=11 puzzle on Friday.