ejolson
Posts: 6622
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code

Fri Feb 19, 2021 4:48 am

ejolson wrote:
Thu Feb 18, 2021 9:50 pm
I'm looking at the code

https://github.com/ednl/aoc2020/blob/main/day22.c

and noticed that if the score of the hands are the same then the cards themselves are assumed the same and in the same order. I'm not sure this is true.
I ran day22.c from the aoc2020 repository on 50,000 randomly generated games, compared the output with pet22.c and found 1315 differences. That means at least one of those programs was wrong

1315 / 50000 = 2.63 percent

of the time.

Here is the Julia script I used to make the input files, if anyone would like to check some more games or programs:

Code: Select all

using Random,Printf
Random.seed!(54321);
for n=1:50000
    g=randperm(50)
    fn=@sprintf("game%05d.dat",n)
    open(fn,"w") do io
        println(io,"Player 1:")
        for i=1:25
            println(io,g[i])
        end
        println(io,"\nPlayer 2:")
        for i=26:50
            println(io,g[i])
        end
    end
end
A deal of cards where they differ is

Code: Select all

Player 1:
47
41
36
39
10
23
40
20
19
31
49
16
17
5
35
7
30
37
32
48
24
38
42
29
15

Player 2:
21
26
45
14
34
44
27
50
8
1
6
12
46
2
13
28
22
25
43
11
18
4
9
3
33
which leads to the output

Code: Select all

$ ./ednl22 
Player 1: 47 41 36 39 10 23 40 20 19 31 49 16 17 5 35 7 30 37 32 48 24 38 42 29 15
Player 2: 21 26 45 14 34 44 27 50 8 1 6 12 46 2 13 28 22 25 43 11 18 4 9 3 33

Part 1
winner : 2
target : 31629
score  : 30844

Part 2
winner : 2
target : 35196
score  : 33566

time  : 0.025873 s
$ ./pet22
Advent of Code Day 22

Part 1 Player 2 won with score 30844
Part 2 Player 2 won with score 32213

Total execution time 0.0982347 seconds.
Used 6804 bytes of 100000 to detect infinite loops.
Note that 33566 is not equal 32213. One of those answers must be wrong, if not both.

Why is it that nothing ever works?

ejolson
Posts: 6622
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code

Fri Feb 19, 2021 6:12 am

ejolson wrote:
Fri Feb 19, 2021 4:48 am
Why is it that nothing ever works?
To shed light on which answer is right and which wrong, I also ran the Go program posted earlier on the same input files. The results

Code: Select all

$ diff pet22.out go22.out | grep "^>" | wc
    925    1850    7400
$ diff pet22.out ednl22.out | grep "^>" | wc
   1315    2630   10440
$ diff go22.out ednl22.out | grep "^>" | wc
   2108    4216   16784
unfortunately provided no light. Could it really still be Advent? My calendar says Lent. What happened to Christmas?

The differences between the results of the Go program and the PET program were

925 / 50000 = 1.85 percent

and the differences between the results of the Go program and the ednl repository code were

2108 / 50000 = 4.215 percent.

In summary,

Code: Select all

   Programs      Difference
go22     pet22      1.85%
pet22    ednl22     2.63%
ednl22   go22       4.22%
Either my Pi 4B hardware has started to malfunction or none of these programs actually work correctly. Does anyone have a solution to day 22 that always gives correct answers?

User avatar
algorithm
Posts: 251
Joined: Mon Nov 25, 2013 9:09 pm
Location: Flatland

Re: Advent of Code

Fri Feb 19, 2021 7:50 am

Ha ha! What an endeavour. Yes, I definitely realised that the score as requested in part 1 had a not insignificant potential for collisions, but I took it as a strong hint that it would be good enough. As it turned out, it was, for me. I think the puzzle maker is quite diligent in providing thoroughly tested input, and I suspect that he tested with his own fallible hashing algorithm that he had just laid out for us. As I read sometimes on the subreddit: the goal is not to solve the general case, but the puzzle in front of you. Of course, the "upping the ante" threads are popular where people go out of their way to generalise and invent completely new challenges.

In his presentation at fosdem he talks a bit about how he makes the puzzles: generally from 19:40, more specifically from 25:15 at https://mirror.as35701.net/video.fosdem ... ofcode.mp4

Edit: I added CRC32 (I fear I used the LSB version, but that doesn't matter as long as we keep it among friends) as an alternative hashing function, also removed some stuff not needed for hashing algo comparison. For my input, it gives the same result. Haven't tried 50,000 random inputs :) See https://github.com/ednl/aoc2020/blob/ma ... testhash.c

ejolson
Posts: 6622
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code

Fri Feb 19, 2021 5:44 pm

algorithm wrote:
Fri Feb 19, 2021 7:50 am
Ha ha! What an endeavour. Yes, I definitely realised that the score as requested in part 1 had a not insignificant potential for collisions, but I took it as a strong hint that it would be good enough. As it turned out, it was, for me. I think the puzzle maker is quite diligent in providing thoroughly tested input, and I suspect that he tested with his own fallible hashing algorithm that he had just laid out for us. As I read sometimes on the subreddit: the goal is not to solve the general case, but the puzzle in front of you. Of course, the "upping the ante" threads are popular where people go out of their way to generalise and invent completely new challenges.
When solving Day 14, I discovered some threads where the problem was generalized with additional floating bits so even large computers wouldn't have enough memory to store every address specified by the masks. To recollect, Day 14 was the puzzle about a docking computer that I solved in Scratch using DeMorgan's laws on sets.

viewtopic.php?p=1794631#p1794631

For Day 22, it appears the input data is simply a deck of cards that has been shuffled and dealt out between two players. I'd be surprised if every deal of cards was screened ahead of time to ensure during the resulting game that the score was a collision-free hash of the state at each turn. Upon rereading the description for Day 22, I don't see any suggestion that the score could be used as a hash either.

At any rate, I've now made some changes to my Go program to make sure it doesn't detect an infinite loop where there wasn't one. Along the way, I discovered some random shuffles of cards which seem to result in very long games. An example is

Code: Select all

Player 1
23
21
30
6
33
48
8
50
36
28
11
45
7
42
4
41
34
9
17
44
26
22
32
37
47

Player 2
39
15
1
49
38
43
40
2
46
10
5
18
35
25
24
29
16
20
12
19
14
27
13
3
31
which on my 2GB Pi 4B now hits swap.

For some reason swap is currently mounted on a network block device over WireGuard, so I'm not expecting an answer very soon. According to the dog developer, gophers tend to collect a lot of stuff in the garbage. I should have known. Fortunately, the above deal of cards is not one for which the other programs obtained different results. I'll retest all the programs soon.
Last edited by ejolson on Fri Feb 19, 2021 7:38 pm, edited 5 times in total.

User avatar
algorithm
Posts: 251
Joined: Mon Nov 25, 2013 9:09 pm
Location: Flatland

Re: Advent of Code

Fri Feb 19, 2021 6:27 pm

I ran my complete code for day 22 on the Pico, which gave:

Part 1: winner = 1, score = 31629, time = 0.00035 s
Part 2: winner = 1, score = 35196, time = 0.09832 s

With the CRC-32 hash it's a bit slower because of extra copying and calculating:

Part 1: winner = 1, score = 31629, time = 0.00035 s
Part 2: winner = 1, score = 35196, time = 0.17132 s

Project at https://github.com/ednl/pico/tree/main/aoc20d22
Somewhat of an improvement on the Python version, although that didn't use the recursion shortcut.

ejolson
Posts: 6622
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code

Fri Feb 19, 2021 9:25 pm

algorithm wrote:
Fri Feb 19, 2021 6:27 pm
I ran my complete code for day 22 on the Pico, which gave:

Part 1: winner = 1, score = 31629, time = 0.00035 s
Part 2: winner = 1, score = 35196, time = 0.09832 s

With the CRC-32 hash it's a bit slower because of extra copying and calculating:

Part 1: winner = 1, score = 31629, time = 0.00035 s
Part 2: winner = 1, score = 35196, time = 0.17132 s

Project at https://github.com/ednl/pico/tree/main/aoc20d22
Somewhat of an improvement on the Python version, although that didn't use the recursion shortcut.
That's not a bad tradeoff for a more reliable hash of the game state.

The Go program doesn't even run on a Pi 4B anymore. Maybe the initial configuration of cards quoted above is triggering some sort of bug in the associative array implementation, since it's inconceivable there could be any more bugs in my code. At any rate, after two and a half hours the run ended with

Code: Select all

$ time ./go22
Advent of Code Day 22

Part 1 Player 1 won with score 32701
runtime: out of memory: cannot allocate 748683264-byte block (2541355008 in use)
fatal error: out of memory

runtime stack:
runtime.throw(0xd467b, 0xd)
    /usr/lib/go-1.11/src/runtime/panic.go:608 +0x5c
runtime.largeAlloc(0x2ca00000, 0x50001, 0xb6f39000)
    /usr/lib/go-1.11/src/runtime/malloc.go:1021 +0x120
runtime.mallocgc.func1()
    /usr/lib/go-1.11/src/runtime/malloc.go:914 +0x38
runtime.systemstack(0x5d980)
    /usr/lib/go-1.11/src/runtime/asm_arm.s:354 +0x84
runtime.mstart()
    /usr/lib/go-1.11/src/runtime/proc.go:1229

goroutine 1 [running]:
runtime.systemstack_switch()
    /usr/lib/go-1.11/src/runtime/asm_arm.s:298 +0x4 fp=0x145f84c sp=0x145f848 pc=0x5da88
runtime.mallocgc(0x2ca00000, 0xc5d68, 0x19260c01, 0x0)
    /usr/lib/go-1.11/src/runtime/malloc.go:913 +0x898 fp=0x145f8b0 sp=0x145f84c pc=0x1a32c
runtime.newarray(0xc5d68, 0x880000, 0x26)
    /usr/lib/go-1.11/src/runtime/malloc.go:1048 +0x5c fp=0x145f8c4 sp=0x145f8b0 pc=0x1a684
runtime.makeBucketArray(0xc0898, 0xb6f39017, 0x0, 0x1e83c, 0x8fb5ed80)
    /usr/lib/go-1.11/src/runtime/map.go:355 +0x170 fp=0x145f8e0 sp=0x145f8c4 pc=0x1b42c
runtime.hashGrow(0xc0898, 0x145fa74)
    /usr/lib/go-1.11/src/runtime/map.go:963 +0x7c fp=0x145f904 sp=0x145f8e0 pc=0x1c650
runtime.mapassign_faststr(0xc0898, 0x145fa74, 0x8fb5ed80, 0x26, 0x17f5a8)
    /usr/lib/go-1.11/src/runtime/map_faststr.go:256 +0x1f4 fp=0x145f934 sp=0x145f904 pc=0x1e9e0
main.dogame(0xc0801, 0x145fc24)
    /x/turb/ejolson/code/aofcode/fuzz/go22.go:125 +0xfc fp=0x145fae4 sp=0x145f934 pc=0xa2e80
main.dogame(0xc0801, 0x14a4dd4)
    /x/turb/ejolson/code/aofcode/fuzz/go22.go:134 +0x260 fp=0x145fc94 sp=0x145fae4 pc=0xa2fe4
main.dogame(0x1, 0xa3574)
    /x/turb/ejolson/code/aofcode/fuzz/go22.go:134 +0x260 fp=0x145fe44 sp=0x145fc94 pc=0xa2fe4
main.part2()
    /x/turb/ejolson/code/aofcode/fuzz/go22.go:161 +0x1c fp=0x145fe88 sp=0x145fe44 pc=0xa33b8
main.main()
    /x/turb/ejolson/code/aofcode/fuzz/go22.go:181 +0xa4 fp=0x145ffc4 sp=0x145fe88 pc=0xa3584
runtime.main()
    /usr/lib/go-1.11/src/runtime/proc.go:201 +0x204 fp=0x145ffe4 sp=0x145ffc4 pc=0x390ec
runtime.goexit()
    /usr/lib/go-1.11/src/runtime/asm_arm.s:867 +0x4 fp=0x145ffe4 sp=0x145ffe4 pc=0x5f7d0

real    163m58.645s
user    28m21.369s
sys 4m28.784s
which makes me think the 32-bit address space of Raspberry Pi OS was exhausted.

For reference, the exact same program completes all 50,000 test cases on an x86 server. Even on the 64-bit machine, that particular test case takes more CPU than all the other 49,999 shuffles of the deck combined.

Next up is to run the CRC hash version of the C code from the repository to see if there are still any differences between the two improved programs. I've improved my C code too, for comparison, but it might have become too memory intensive to actually run on a PET.

ejolson
Posts: 6622
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code

Sat Feb 20, 2021 12:18 am

ejolson wrote:
Fri Feb 19, 2021 9:25 pm
Next up is to run the CRC hash version of the C code from the repository to see if there are still any differences between the two improved programs. I've improved my C code too, for comparison, but it might have become too memory intensive to actually run on a PET.
I've now run the improved C program with the CRC hash, the improved Go program that takes gigabytes of RAM and the improved version of the pet-friendly C program that now uses over 32 kilobytes of memory on the same 50,000 random shuffles of the deck of cards. The results

Code: Select all

$ diff newgo.out newcrc.out | grep '^>' | wc
      3       6      24
$ diff newcrc.out newpet.out | grep '^>' | wc
      3       6      24
$ diff newpet.out newgo.out | grep '^>' | wc
      0       0       0
indicate there is now only a

3 / 50000 =0.006 percent

difference in output between the programs. While not good enough for a tier 4 datacenter, the results are much closer than before. Note the fact that the Go and the pet-friendly codes now produce identical answers isn't such a big deal since one is a translation of the other.

Here is a shuffle where the programs give different answers

Code: Select all

Player 1
38
43
12
35
26
34
48
23
36
25
46
19
37
41
47
14
39
40
21
2
9
31
15
16
1

Player 2
30
33
7
32
45
22
17
10
29
5
11
20
49
6
44
42
24
3
27
50
13
4
28
18
8
My guess is that the 32-bit CRC hash is still colliding and creating incorrect answers; however, to be certain would require someone to run the above input on their own code to see whether they get the pet-friendly output

Code: Select all

$ ./newpet22 ; # run on an EPYC 7371
Advent of Code Day 22

Part 1 Player 2 won with score 33947
Part 2 Player 2 won with score 33599

Total execution time 0.00601436 seconds.
Used 11284 bytes of 300000 to detect infinite loops.
or something else.

User avatar
algorithm
Posts: 251
Joined: Mon Nov 25, 2013 9:09 pm
Location: Flatland

Re: Advent of Code

Sat Feb 20, 2021 2:18 am

Funnily enough, my old part1-score-hash gave the correct (PET) answer here. Confirmed by switching G-polynomial: both Castagnoli and Koopman also gave the PET answer. Values from https://en.wikipedia.org/wiki/Cyclic_re ... ncy_checks

ejolson
Posts: 6622
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code

Sat Feb 20, 2021 4:09 am

algorithm wrote:
Sat Feb 20, 2021 2:18 am
Funnily enough, my old part1-score-hash gave the correct (PET) answer here. Confirmed by switching G-polynomial: both Castagnoli and Koopman also gave the PET answer. Values from https://en.wikipedia.org/wiki/Cyclic_re ... ncy_checks
I think the moral of the story is that a 32-bit hash has

2^32 = 4294967296

possible values, while the number of possible shuffles of a 50 card deck are

50! = 30414093201713378043612608166064768844377641568960512000000000000

Although not all possible arrangements of cards will appear during a game, it appears unlikely to me that any 32-bit hash could work reliably for all those different games.

Still, I'm actually surprised that randomly checking 50000 games so easily finds cases where the results are wrong. I think many programs which eventually produce wrong answers appear to work reliably when subjected to much larger test cases. In my opinion, this is why any type of quality assurance that doesn't also audit the source code is unlikely to provide the needed guarantees of reliability when used for security, banking or solving Advent of Code puzzles.

Earlier this afternoon, when I asked what proportion of published solutions to Day 22 suffer similar problems, Fido punctuated my question with a question bark: Why the delay? Have you still not figured out how to solve Day 23 using a Pico? I explained that 264KB might seem like a lot of memory, but problem sizes have also become larger as computers more powerful.

At this the dog developer snorted, the PET has less than 32KB but was able to analyze all the data about the origins of the epidemic uncovered by the WHO. How could an Advent of Code puzzle be any more difficult?

User avatar
algorithm
Posts: 251
Joined: Mon Nov 25, 2013 9:09 pm
Location: Flatland

Re: Advent of Code

Sat Feb 20, 2021 4:51 pm

ejolson wrote:
Sat Feb 20, 2021 4:09 am
I think the moral of the story is that a 32-bit hash has

2^32 = 4294967296

possible values, while the number of possible shuffles of a 50 card deck are

50! = 30414093201713378043612608166064768844377641568960512000000000000
Sure, yes. Obviously the solution is to store the complete game state! Or, my final try, use a 64-bit CRC hash: https://github.com/ednl/aoc2020/blob/ma ... testhash.c (now properly MSB, not that there's anything wrong with LSB)

ejolson
Posts: 6622
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code

Sat Feb 20, 2021 6:45 pm

algorithm wrote:
Sat Feb 20, 2021 4:51 pm
ejolson wrote:
Sat Feb 20, 2021 4:09 am
I think the moral of the story is that a 32-bit hash has

2^32 = 4294967296

possible values, while the number of possible shuffles of a 50 card deck are

50! = 30414093201713378043612608166064768844377641568960512000000000000
Sure, yes. Obviously the solution is to store the complete game state! Or, my final try, use a 64-bit CRC hash: https://github.com/ednl/aoc2020/blob/ma ... testhash.c (now properly MSB, not that there's anything wrong with LSB)
Storing the complete game state is what the improved Go code does, and likely why it no longer runs in 2GB on the Pi 4B. The PET version stores the complete state only for the base game but not for the recursive games, that's because it's only necessary to find the exact moment the game repeats for the scoring.

Unfortunately, the PET version is no longer pet friendly and Fido has been complaining. According to the canine coder, the weather in the dog house has changed from the I've got a bigger nuclear button approach back to trust but verify in accordance with the political climate. After thinking a moment I asked, does that mean we can now use a 32-bit CRC to detect infinite loops as long the the match is verified later? In reply the developer growled, what's the point of a cat redundancy check now that the MEOW™ attachment is finished and in production?

ejolson
Posts: 6622
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code

Sat Feb 20, 2021 9:31 pm

algorithm wrote:
Sat Feb 20, 2021 4:51 pm
ejolson wrote:
Sat Feb 20, 2021 4:09 am
I think the moral of the story is that a 32-bit hash has

2^32 = 4294967296

possible values, while the number of possible shuffles of a 50 card deck are

50! = 30414093201713378043612608166064768844377641568960512000000000000
Sure, yes. Obviously the solution is to store the complete game state! Or, my final try, use a 64-bit CRC hash: https://github.com/ednl/aoc2020/blob/ma ... testhash.c (now properly MSB, not that there's anything wrong with LSB)
The new CRC version of the code is now running, this time on 500000 test cases which still may not be enough as the chances of finding a collision that affects the outcome could be vanishingly small.

At Fido's insistence I've been looking at how to run Day 23 on the Pico 64, which is an 8 by 8 array of Pi Pico computers connected together using a proprietary 2D networking fabric developed in doghouse. According to the head of new silicon and coronavirus mask design, there are supply-chain shortages related to an insufficient stock of F35 fighter jets as well as RP2040 micro controllers, so expect delays.

As a result, my current plan is to adapt the Go program

Code: Select all

/*  advent of code day 23 https://adventofcode.com/2021/day/23
    written february 15, 2020 by eric olson */

package main
import ("fmt"; "os"; "time"; "bufio")

type circle []int
var cups,day23 circle
var csize,current int
var tictime float64

func tic() {
    now:=time.Now()
    tictime=float64(now.Unix())+1.0E-9*float64(now.Nanosecond())
}
func toc() float64 {
    now:=time.Now()
    return float64(now.Unix())+1.0E-9*float64(now.Nanosecond())-tictime
}

func doinit() {
    raw,err:=os.Open("day23.dat")
    if err!=nil {
        fmt.Printf("Error opening day23.dat for import!\n")
        os.Exit(1)
    }
    fp:=bufio.NewScanner(raw)
    if !fp.Scan() {
        fmt.Printf("Error reading initial circle of cups!\n")
        os.Exit(1)
    }
    s:=fp.Text()
    day23=make(circle,len(s))
    for i:=0;i<len(s);i++ { day23[i]=int(s[i]-'0') }
    raw.Close()
}

func prans() {
    j:=cups[1]
    for i:=1; i<csize; i++ {
        fmt.Printf("%d",j)
        j=cups[j]
    }
    fmt.Printf("\n")
}

func ishere(c int) bool {
    j:=current
    for i:=0; i<3; i++ {
        j=cups[j]
        if j==c { return false }
    }
    return true
}

func shuffle() {
    next:=current
    for {
        next=(next+csize-2)%csize+1
        if ishere(next) { break }
    }
    j:=cups[current]
    k:=cups[cups[j]]
    cups[current]=cups[k]
    cups[k]=cups[next]
    cups[next]=j
    current=cups[current]
}

func part1() {
    csize=len(day23)
    cups=make(circle,csize+1)
    for i:=0; i<csize; i++ {
        cups[day23[i]]=day23[(i+1)%csize]
    }
    current=day23[0]
    for t:=0;t<100;t++ { shuffle() }
    fmt.Printf("Part 1 The labels on the cups were ")
    prans()
}

func part2() {
    csize=1000000
    cups=make(circle,csize+1)
    var i int
    for i=0; i<len(day23)-1; i++ {
        cups[day23[i]]=day23[i+1]
    }
    cups[day23[i]]=i+2
    for i=len(day23)+1; i<csize; i++ {
        cups[i]=i+1
    }
    cups[i]=day23[0]
    current=day23[0]
    for t:=0;t<10000000;t++ { shuffle() }
    fmt.Printf("Part 2 The star product is %d\n",
        int64(cups[1])*int64(cups[cups[1]]))
}

func main() {
    tic()
    fmt.Printf("Advent of Code Day 23\n\n")
    doinit()
    part1()
    part2()
    fmt.Printf("\nTotal execution time %g seconds.\n",toc())
    os.Exit(0)
}
which currently runs on a 4B as

Code: Select all

$ ./day23
Advent of Code Day 23

Part 1 The labels on the cups were 45798623
Part 2 The star product is 235551949822

Total execution time 1.5338306427001953 seconds.
to a distributed memory design using of 64 cooperating tasks.

For simplicity of debugging, my idea is to first model each Pico using a different Go routine and simulate communication over the proprietary networking fabric using channels. With luck this will be the first time ever in history where the software is ready before the hardware.

User avatar
algorithm
Posts: 251
Joined: Mon Nov 25, 2013 9:09 pm
Location: Flatland

Re: Advent of Code

Sat Feb 20, 2021 10:15 pm

Nice. I thought about linking up a few Picos. No need for distributed algorithms, I think; just distributed data. And they do have 2 MB of flash memory, so probably not 2 but definitely 3 would suffice, I suppose. (Because counting+storing to 1 million takes about 4 MB.)

ejolson
Posts: 6622
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code

Sat Feb 20, 2021 11:43 pm

algorithm wrote:
Sat Feb 20, 2021 10:15 pm
Nice. I thought about linking up a few Picos. No need for distributed algorithms, I think; just distributed data. And they do have 2 MB of flash memory, so probably not 2 but definitely 3 would suffice, I suppose. (Because counting+storing to 1 million takes about 4 MB.)
That's right. There won't be any parallel processing going on, but only clustering to obtain a larger distributed memory.

I thought about using the 2MB flash of the Pico but worried 10,000,000 turns might lead to excessive wear. Of course that would be distributed throughout the flash device, but due to lack of data locality one might still end up with about 10,000,000 erase cycles.

In other news, woohoo, the 64-bit CRC code for Day 22 agrees with the improved PET program on 500,000 randomized inputs. While that's only

500,000 / 50! = 1.6E-57 percent

of the input space, the results seem to have satisfied Fido, who is now busy patching KiCad. When I suggested the free version of Eagle might be easier, the designer replied that pets don't usually do graphics, so it's necessary to modify the source to enable the Commodore High Speed Graphik card.

http://www.6502.org/users/sjgray/comput ... index.html

I think the Pico 64 will take a very long time to finish.

ejolson
Posts: 6622
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code

Sun Feb 21, 2021 9:12 pm

ejolson wrote:
Sat Feb 20, 2021 11:43 pm
I think the Pico 64 will take a very long time to finish.
Development has progressed. I have a mock up communications system between Go routines that uses channels to emulate everything except the errors and latency one might expect with an SPI interconnect between two Picos. Since there are two SPI blocks on each micro-controller and assuming the PIO can act as a slave, this means it should be easy to arrange the Picos into a 2D torus without a daisy chain or multiplexing.

According to the head of marketing, the SPI interconnect will operate at a speed of 64 MHz to keep with the 64 themed naming. Fortunately Fido no longer has paw-print (signature) authority, otherwise the circular filing cabinet would already be filled with a mess of twisted wires. I'm assured, however, unlike the prototype that the version designed using KiCad will consist of a compact 8x8 array of RP2040's wave-soldered to a single circuit board.

I'm expecting to rediscover why nobody liked programming the Connection Machine.

https://en.wikipedia.org/wiki/Connection_Machine

Would a 6D hypercube interconnect be possible instead of an 8x8 torus?

lurk101
Posts: 395
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Advent of Code

Sun Feb 21, 2021 11:17 pm

ejolson wrote:
Sun Feb 21, 2021 9:12 pm
According to the head of marketing, the SPI interconnect will operate at a speed of 64 MHz to keep with the 64 themed naming.
Err.. Good luck running SPI at 64MHz. Ordered 16 to make a 4-cube.

ejolson
Posts: 6622
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code

Sun Feb 21, 2021 11:23 pm

lurk101 wrote:
Sun Feb 21, 2021 11:17 pm
ejolson wrote:
Sun Feb 21, 2021 9:12 pm
According to the head of marketing, the SPI interconnect will operate at a speed of 64 MHz to keep with the 64 themed naming.
Err.. Good luck running SPI at 64MHz. Ordered 16 to make a 4-cube.
Sounds like a Pico 16. Are you planning to run SPI at 16 MHz then?

lurk101
Posts: 395
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Advent of Code

Sun Feb 21, 2021 11:28 pm

ejolson wrote:
Sun Feb 21, 2021 11:23 pm
lurk101 wrote:
Sun Feb 21, 2021 11:17 pm
ejolson wrote:
Sun Feb 21, 2021 9:12 pm
According to the head of marketing, the SPI interconnect will operate at a speed of 64 MHz to keep with the 64 themed naming.
Err.. Good luck running SPI at 64MHz. Ordered 16 to make a 4-cube.
Sounds like a Pico 16. Are you planning to run SPI at 16 MHz then?
Best I ever got out of SPI on a Pi is about 1MHz.

ejolson
Posts: 6622
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code

Mon Feb 22, 2021 3:47 am

lurk101 wrote:
Sun Feb 21, 2021 11:28 pm
Ordered 16 to make a 4-cube.
The chief technical officer and rabbit hole explorer just reassured me that SPI on a Pico goes much faster than 1 MHz and then sent me a diagram of the planned network topology for a hypercube version of the Pico 64.

Image

Obviously the Pico 64 is cancelled. On the other hand a 4D hypercube

Image

seems quite reasonable, so a Pico 16 could be a win.

The question remains, however, whether a 16-node Pico cluster will have enough distributed memory to solve the Day 23 puzzle for a proper game of crab cups.

Using 3-byte integers maybe it will work .
Last edited by ejolson on Mon Feb 22, 2021 6:28 pm, edited 2 times in total.

lurk101
Posts: 395
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Advent of Code

Mon Feb 22, 2021 1:39 pm

The 6-cube would provide much more memory. At only 6 interconnects per node, 8 PIO channels should suffice.

User avatar
algorithm
Posts: 251
Joined: Mon Nov 25, 2013 9:09 pm
Location: Flatland

Re: Advent of Code

Tue Feb 23, 2021 1:56 pm


ejolson
Posts: 6622
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code

Wed Feb 24, 2021 7:03 am

algorithm wrote:
Tue Feb 23, 2021 1:56 pm
Well, this changes everything. https://www.raspberrypi.org/blog/how-to ... y-pi-pico/
I wonder how much RAM Fuzix leaves for an actual program. Do you think Fuzix would consume so much memory that a Pico 64 would not be enough for crab cups and a Pico 256 would be needed? Assuming eight channels of PIO work to connect each Pico to eight others, one could then connect them in a 8D hypercube and have more than plenty of distributed memory. After that all that would be needed is a version of parallel C* that runs under Fuzix.

http://people.csail.mit.edu/bradley/cm5 ... sGuide.pdf
http://people.csail.mit.edu/bradley/cm5 ... gGuide.pdf

In other news, cancellation of the 6D hypercube seems to have inspired a new design based on a 4 by 4 by 4 torus in 3D. Unfortunately, the Pico 64 Mark II has an interconnect that looks like

Image

The chief technical officer and rabbit hole explorer claims the torus is a better match for deep-learning convolutional neural networks, but I can't tell the difference. Could it be the torus and hypercube are the same? In either case, maybe Fido's persistence will pay off.

lurk101
Posts: 395
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Advent of Code

Wed Feb 24, 2021 2:44 pm

algorithm wrote:
Tue Feb 23, 2021 1:56 pm
Well, this changes everything. https://www.raspberrypi.org/blog/how-to ... y-pi-pico/
Why must some form of Unix(tm) be ported to every device in existence? Cute, but is it really a good fit?

lurk101
Posts: 395
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Advent of Code

Wed Feb 24, 2021 4:53 pm

ejolson wrote:
Wed Feb 24, 2021 7:03 am
The chief technical officer and rabbit hole explorer claims the torus is a better match for deep-learning convolutional neural networks, but I can't tell the difference. Could it be the torus and hypercube are the same? In either case, maybe Fido's persistence will pay off.
Ah, but I want full duplex interconnects, so 2 PIOs per and a maximum of 4 interconnects per node. Is there an optimal topology?

ejolson
Posts: 6622
Joined: Tue Mar 18, 2014 11:47 am

Re: Advent of Code

Wed Feb 24, 2021 4:58 pm

lurk101 wrote:
Wed Feb 24, 2021 2:44 pm
algorithm wrote:
Tue Feb 23, 2021 1:56 pm
Well, this changes everything. https://www.raspberrypi.org/blog/how-to ... y-pi-pico/
Why must some form of Unix(tm) be ported to every device in existence? Cute, but is it really a good fit?
From what I understand, the first version of the Unix operating system

https://github.com/DoctorWkt/pdp7-unix

was a self-hosting software development environment written in assembler to run on a PDP-7 with a 1MB hard disk.

While later versions were written in C and marketed as a document processing system, the main idea was always to be a software development environment. In particular, compilers for multiple languages were included from the beginning along with debuggers, editors and archivers as well as tools to search programs made of source code spread over multiple files, difference them and track the revisions.

Unfortunately, Fuzix is not self hosting and lacks even a C compiler. In a way Fuzix is a proof how important the gcc compiler was for Linux to be anything like Unix. That's because without a compiler you do not have a development environment at all, let alone a convenient one--the whole point of Unix, why Linus wrote Linux and one of the main reasons Linux was chosen to teach programming on the Raspberry Pi.

On the other hand, it might be nice to have an execution environment suitable to run POSIX compliant code on a Pico.

Return to “General programming discussion”