as parallel mergesort would be too slow
, there is only one suitable algorithm remaining.Jeux du Sort Vite
Jeux du Sort Vite
I have started working on it, I bet I know the algorithm used by the best solver
as parallel mergesort would be too slow, there is only one suitable algorithm remaining.
as parallel mergesort would be too slow
, there is only one suitable algorithm remaining.-
AMindForeverVoyaging
- Forum Admin
- Posts: 497
- Joined: Sat May 28, 2011 9:14 am
- Location: Germany
Re: Jeux du Sort Vite
Honestly I don't think that anyone is working on this challenge except for you... it's been almost five years since the last person solved it.Hippo wrote:I bet I know the algorithm used by the best solver
Sure I have the algorithm in mind and it's just matter of writing it down I just hope it would be fast enough ...
Yes it's shvm time for me now
.
Hmm, I am far from finishing the running version, but it seems I would be roughly at 304
. Or may be 330:(.
Damn ... codding when one tries to make almost optimal solution on first try is so slow ... I have spent spare time of about 14 days on it already and I am still in the first third of execution time...
I have the algorithm in mind and it's just matter of writing it down I just hope it would be fast enough ... Yes it's shvm time for me now
.Hmm, I am far from finishing the running version, but it seems I would be roughly at 304
. Or may be 330:(.I take it back, mergesort variant for boolean circuits does not look that bad.Hippo wrote:I have started working on it, I bet I know the algorithm used by the best solver
as parallel mergesort would be too slow
Damn ... codding when one tries to make almost optimal solution on first try is so slow ... I have spent spare time of about 14 days on it already and I am still in the first third of execution time...
Last edited by Hippo on Sat Mar 05, 2016 1:52 pm, edited 1 time in total.
Surprisingly I still work on this challenge ... after a lot of work I have about half of code implemented (and tested) ... I never spent so much time on codding single code ... and especially here when there is no use of it .
Problem is I am not trying to write a solution, but close to optimal solution ... .
Uff, I have finished codding ... I could beat cutter but I dont want to make the hill steeper so I put nop operations to the code.
Last small challenge is to submit the solution ... tomorrow.
.Problem is I am not trying to write a solution, but close to optimal solution ... .
Uff, I have finished codding ... I could beat cutter but I dont want to make the hill steeper so I put nop operations to the code
.Last small challenge is to submit the solution ... tomorrow.
OK this challenge required a lot of stamina ... the excell svhm was good start for debugging, I have implemented different logging sheets used during development.
The sync optimization problems would be hard to debug without such support.
I have not used code generator.
I was writing "packed linear version of parallel code", translated to SVHM version by hand during the debugging.
I had used 3 criterias of ordering rows of the linear code during the development ... SVHM topology, time(thread invocation order), and algorithm specific one used to simplify next stage planning.
For one given input I had manually computed expected comparator inputs. And I have carefully debugged synchronization of each stage before entering next level.
Even after the code worked on given input there were (at least) 3 bugs remaining in the code.
One was missing char in the code in not used branch, but 2 were more important as there was insufficient wait for branch which was not invoked in the tested input (in both cases the same tick, but wrong thread order). Fortunately both bugs were in noncritical sections (the threads had to sync wait just few ticks later anyways).
I have tested final code on about 18 permutations, but code coverage is not 100% even now
(about 35 comparators were not used for sync praoblematic inputs on the test cases).
The linear code should have been tested by comp, but the notation developped during it's writing
and it would be a lot of work to convert it to the final notation.
The rules at starting phases when thread codes are near each other differ a bit to rules at later phases so even the automatic checking would be problematic.
I have not remembered the cutter's time well so I have spent some time (maybe 2hours) to speed up last 2 ticks to reach 265 ... and than I have found he had 267. I think reaching 263 would require reorganizing only of the output section of code. I bet 260 or less could be done with better memory management to the one I have chosen on the second try (slightly optimized from the first one).
The sync optimization problems would be hard to debug without such support.
I have not used code generator.
I was writing "packed linear version of parallel code", translated to SVHM version by hand during the debugging.
I had used 3 criterias of ordering rows of the linear code during the development ... SVHM topology, time(thread invocation order), and algorithm specific one used to simplify next stage planning.
For one given input I had manually computed expected comparator inputs. And I have carefully debugged synchronization of each stage before entering next level.
Even after the code worked on given input there were (at least) 3 bugs remaining in the code.
One was missing char in the code in not used branch, but 2 were more important as there was insufficient wait for branch which was not invoked in the tested input (in both cases the same tick, but wrong thread order). Fortunately both bugs were in noncritical sections (the threads had to sync wait just few ticks later anyways).
I have tested final code on about 18 permutations, but code coverage is not 100% even now
(about 35 comparators were not used for sync praoblematic inputs on the test cases).
The linear code should have been tested by comp, but the notation developped during it's writing
and it would be a lot of work to convert it to the final notation.
The rules at starting phases when thread codes are near each other differ a bit to rules at later phases so even the automatic checking would be problematic.
I have not remembered the cutter's time well so I have spent some time (maybe 2hours) to speed up last 2 ticks to reach 265 ... and than I have found he had 267. I think reaching 263 would require reorganizing only of the output section of code. I bet 260 or less could be done with better memory management to the one I have chosen on the second try (slightly optimized from the first one).