Go to Post The size of your team has nothing to do with the size of your heart. - Amanda Morrison [more]
Home
Go Back   Chief Delphi > Technical > Programming
CD-Media   CD-Spy  
portal register members calendar search Today's Posts Mark Forums Read FAQ rules

 
Closed Thread
Thread Tools Rating: Thread Rating: 83 votes, 5.00 average. Display Modes
  #16   Spotlight this post!  
Unread 11-12-2014, 18:15
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,141
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: OPR Programming Challenge

Quote:
Originally Posted by Michael Hill View Post
...the second (around the for loop) is ~0.235 sec
I wonder would happen if you wrote that in C and compiled it to a callable routine.


  #17   Spotlight this post!  
Unread 13-12-2014, 21:02
Greg McKaskle Greg McKaskle is offline
Registered User
FRC #2468 (Team NI & Appreciate)
 
Join Date: Apr 2008
Rookie Year: 2008
Location: Austin, TX
Posts: 4,766
Greg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond repute
Re: OPR Programming Challenge

I've been a bit busy, but since the light is at the end of the tunnel, I met with Jim, a mathematician on our team to see if he would do this with our sparse matrix tools. The first screenshot shows the breakdown of times. The second is the code written in LV.

He is going to tinker to see if he can find a better way to build the sparse matrix, since most of the time is spent before invoking the solver.

This was timed on a Windows VM that has 4 cores running on my macbook 2.7GHz core i7. Jim was running on a desktop machine which I don't have details for, and he wasn't writing the file. His was somewhat faster. My cores are only about 70% utilized since most of the time isn't spent in the solver.

Greg McKaskle
Attached Thumbnails
Click image for larger version

Name:	From Clipboard.png
Views:	75
Size:	24.4 KB
ID:	17585  Click image for larger version

Name:	From Clipboard2.png
Views:	60
Size:	307.3 KB
ID:	17586  
  #18   Spotlight this post!  
Unread 14-12-2014, 19:31
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,141
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: OPR Programming Challenge


OK guys.

I just wrote, compiled, and ran a 32-bit single-core native app on an 8-year-old Pentium D machine running 32-bit XP Pro SP3, and timed it using RDTSC instructions embedded in the code.

It took 11.9 milliseconds to read the raw data file (cached in RAM) and generate the alliance score vectors and the sparse design matrix.

Using 16-bit unsigned integers for the team numbers and scores, generating the sparse matrix directly from the raw data, and compiling to native code saves a lot of runtime.



Last edited by Ether : 15-12-2014 at 17:46. Reason: add detail
  #19   Spotlight this post!  
Unread 15-12-2014, 18:56
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,141
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: OPR Programming Challenge

Quote:
Originally Posted by Ether View Post
I just wrote, compiled, and ran a 32-bit single-core native app on an 8-year-old Pentium D machine running 32-bit XP Pro SP3, and timed it using RDTSC instructions embedded in the code.
Here's the Delphi code. I wonder how fast it would run on a modern 64-bit machine. Maybe somebody would like to port it to C and try it.
Attached Files
File Type: pdf At&b.pdf (28.0 KB, 39 views)
  #20   Spotlight this post!  
Unread 18-12-2014, 15:29
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,141
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: OPR Programming Challenge

Quote:
Originally Posted by Ether View Post
Here's the Delphi code. I wonder how fast it would run on a modern 64-bit machine. Maybe somebody would like to port it to C and try it.
Based on some PMs I have received, I should clarify a few things.
  • The posted Delphi code reads the raw 8-column (r1 r2 r3 b1 b2 b3 rs bs) whitespace-delimited alliance scores text data file (from cached RAM) and constructs two matrices [At] and [b]. It takes ~12ms to do this on an 8-year-old Pentium D machine.

  • [A]=[At]' is the the binary design matrix

  • [b] is the matrix of alliance scores (not the team OPR scores)

  • [A][x]≈[b] is the overdetermined system of linear equations

  • [A][x]≈[b] can be solved with one line of code in Octave (or MatLab) as follows: [x]=[A]\[b]. [x] will be the matrix whose column vectors minimize the sum of the squares of the corresponding column vectors in the residuals matrix [r]=[b]-[A][x]

  • But it is much faster (and acceptably stable and accurate for OPR purposes) to create and solve the Normal Equations [N][x]=[d] instead

  • [N] and [d] can be formed from [At] and [b] as follows: [N]=[At][At]' and [d]=[At][b]

  • [N][x]=[d] can be solved with one line of code in Octave (or MatLab) as follows: [x]=[N]\[d]

  • solving [N][x]=[d] is faster than solving [A][x]≈[b] because 1) [N] is a smaller matrix than [A], and 2) N is symmetric positive definite so Cholesky factorization can be used

  • the computations [A]=[At]', N=[At][A], and [d]=[At][b] take about 20ms on the 8-year-old Pentium D machine

  • the Normal Equations solution [x]=[N]\[d] takes about 210ms on the 8-year-old Pentium D machine, using a single core

  • there may be Cholesky factoring algorithms which would permit multiple cores to be used for factoring

See this post for some additional details:
http://www.chiefdelphi.com/forums/sh...00#post1404300

  #21   Spotlight this post!  
Unread 19-12-2014, 22:32
Greg McKaskle Greg McKaskle is offline
Registered User
FRC #2468 (Team NI & Appreciate)
 
Join Date: Apr 2008
Rookie Year: 2008
Location: Austin, TX
Posts: 4,766
Greg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond repute
Re: OPR Programming Challenge

Less busy now, so I met with Jim a few we made a few more passes. The attached image shows the top level LV diagram. And the zip has the code saved in LV 2014. The other image shows the time breakdown for the different portions.

The code runs in around 20ms on my laptop running a VM. It iterates until the residual is about 3 digits after the decimal.

Building the sparse matrix creates the diagonal terms and upper portion independently, which substantially speeds the elimination of duplicate terms. The complete solver was swapped out for one based on conjugate gradient.

The commented code loads from disk, the enabled code has the data in RAM, in a constant. Loading from disk adds another 20ms.

Greg McKaskle
Attached Thumbnails
Click image for larger version

Name:	From Clipboard 4.png
Views:	14
Size:	329.5 KB
ID:	17609  Click image for larger version

Name:	From Clipboard 5.png
Views:	16
Size:	105.8 KB
ID:	17612  
Attached Files
File Type: zip OPR Solution.zip (295.5 KB, 4 views)
  #22   Spotlight this post!  
Unread 19-12-2014, 22:59
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,141
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: OPR Programming Challenge

Quote:
Originally Posted by Greg McKaskle View Post
Less busy now, so I met with Jim a few we made a few more passes. The attached image shows the top level LV diagram. And the zip has the code saved in LV 2014. The other image shows the time breakdown for the different portions.
Thanks for posting this Greg. Very impressive performance.

Quote:
It iterates until the residual is about 3 digits after the decimal.
What did you use for the initial guess for the iterative solver?


  #23   Spotlight this post!  
Unread 20-12-2014, 07:11
Greg McKaskle Greg McKaskle is offline
Registered User
FRC #2468 (Team NI & Appreciate)
 
Join Date: Apr 2008
Rookie Year: 2008
Location: Austin, TX
Posts: 4,766
Greg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond reputeGreg McKaskle has a reputation beyond repute
Re: OPR Programming Challenge

The initial guess is the zero vector. It takes 11 iterations to converge.

Greg McKaskle
Closed Thread


Thread Tools
Display Modes Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump


All times are GMT -5. The time now is 00:18.

The Chief Delphi Forums are sponsored by Innovation First International, Inc.


Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Copyright © Chief Delphi