Sudoku-algoritme oversat til over 50 parallelle kerner på to timer

Intels væsentligste salgsargument for den nye Xeon Phi-platform er en lettere vej til parallel databehandling. I praksis er det dog ikke blot et tryk på en knap.
Illustration: Jesper Stein Sandal

HAMBORG. Intels nye Xeon Phi skal konkurrere med især Nvidias og AMD's grafikprocessorer i kapløbet om at levere ekstra regnekraft til supercomputersystemer. Intels stærkeste kort skal være en let tilgængelighed for programmørerne, men i praksis skal der stadig arbejdes for at udnytte Xeon Phi.

Xeon Phis mere end 50 kerner kan ganske vist betragtes som x86-kerner, men ligesom med alle andre parallelle systemer, så kan man ikke automatisk høste hele potentialet uden at bruge knofedt på at optimere koden.

»Det tog kun to timer at skrive det parallelle ind i programmet,« fortæller chefsoftwarearkitekt Gilles Civario fra Irish Centre for High-End Computing til Version2.

Sammen med to andre forskere arbejder han med parallel databehandling og demonstrerede mulighederne ved Xeon Phi med et program, som kan finde unikke løsninger ud fra sudokuer med 17 tal.

På den samme arbejdsstation kunne han køre to forskellige versioner af algoritmen. Den ene, var forskernes oprindelige algoritme optimeret til Intels Xeon-processor, og den anden var den nye version, hvor algoritmen var den samme, men resten af programmet ændret til at udnytte de mange kerner i Xeon Phi.

Derfra var der dog stadig langt i mål. Selve programmet var omskrevet til Xeon Phi-platformen på to dage, men derefter to det stadig et par uger med optimering af koden.

»Jeg vil tro, at der stadig er plads til en forbedring på op til 50 procent,« siger Gilles Civario.

Parallel databehandling har det seneste årti været løsningen på at få supercomputerkapaciteten til at vokse hurtigere end Moores lov takket være processorer med flere kerner.

Den løsningsmodel har de seneste år taget et ekstra spring, efter de kraftige grafikprocessorer, som oprindeligt er udviklet til 3D-beregninger, er blevet taget i brug som supplement til de almindelige processorer.

På supercomputerkonference ISC i Hamborg i denne uge demonstrerede både AMD, Nvidia og Intel deres bud på, sådan en ekstra regnekraft. Intels skiller sig ud ved dels endnu kun at være på prototypestadiet og dels ved at bygge på dele af x86-arkitekturen snarere end at udspringe fra 3D-markedet.

Parallel databehandling er imidlertid udfordrende, når man skal skrive software til at udnytte et stort antal processorkerner pr. server eller node i en supercomputer.

Derfor arbejder Intel også sammen med flere leverandører af software til eksempelvis simulering for at indbygge muligheden for at slå udnyttelse af Intels nye Xeon Phi-indstikskort til i programmerne.

Version2's rejse til Hamborg er betalt af Intel.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Kommentarer (10)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Jens Madsen

Kan programmerne ikke skrives i et sprog, der tillader automatisk parallelisering? Det vil gøre det nemmere, hvis softwaren ikke skal ændres og tilpasses computerens hardware, men fungerer uden modifikation, uanset hvor mange parallele processorer, der er til rådighed på et givet tidspunkt.

Formålet i et højniveau-sprog, er at gøre det hardware uafhængigt. En manglende hardware uafhængighed, med hensyn til parallelisme, er ret alvorligt, og en fundemental fejl ved et højniveau sprog. Måske kan et sådant sprog, end ikke kaldes høj-niveau sprog, da det er låst fast til en bestemt arkitektur med en given parallelisme, og altså arkitektur låst.

Filosofien med høj-niveau sprog, er at opgaven beskrives overfor compileren, mens at optimeringer, oversættelse til binær kode, parallelisering, og alt andet "nørdet" optimering, overlades til compileren. Dermed også paralleliseringen. Hvis sproget ikke lever op til det, er det mere et mellem-nivau sprog.

Brian Højen-Sørensen

Det lyder ret fedt. Bruger i øjeblikket en dual xeon (24 kerner) maskine, som jo så kan udvides til 74 kerner uden yderligere dikkedarer. Det er ikke dumt.

Det er hvad jeg kalder en budget "supercomputer", hvis ellers prisen ikke er helt ude i hampen.

Man må antage at Intels egne compilere (Fortran og C++) virker nogenlunde out of the box.

Torben Mogensen Blogger

Et program til at løse sudokuer burde ikke fylde mere end 50-150 linjer afhængig af sprog m.m. Så at det tager to timer at skrive det om til at udnytte kernerne (og yderligere et par uger til at optimere det til at udnytte kernerne nogenlunde fornuftigt) lyder bestemt ikke lovende.

Jeg tror i det hele taget ikke meget på ideen om, at man kan tage et allerede skrevet C program og modificere det em smule, så det kører parallelt. Enten skal programmet skrives fra grunden til en bestemt parallel arkitektur, eller det skal skrives i et sprog, der ikke overspecificerer rækkefølge eller datadeling. Og selv da er parallelisering ikke automatisk -- det er blot lettere.

Jens Madsen

Jeg tror i det hele taget ikke meget på ideen om, at man kan tage et allerede skrevet C program og modificere det em smule, så det kører parallelt. Enten skal programmet skrives fra grunden til en bestemt parallel arkitektur, eller det skal skrives i et sprog, der ikke overspecificerer rækkefølge eller datadeling. Og selv da er parallelisering ikke automatisk -- det er blot lettere.

Det er ikke et stort problem, at analysere triviel sekventiel kode, og omskrive det, til et ikke sekventielt sprog. Problemet med C++, tror jeg, i højere grad, er selve det at analysere koden, således den kan behandles. Brugen af pointere, måden som OOP fungerer, osv. tror jeg, reelt er det, som giver datalogerne hovedpine.

Almindeligt sekventiel kode med variable, er relativt nemt at behandle. Arrays, med variable index's er langt sværre. Og pointer variable - det er noget bøvl, da det kan betragtes som et stort array, med et kæmpe variabel index. Et sådant array, tvinger på mange måde rækkefølgen af koden, fordi det er svært analyserbart. Man kan dele det op i læse og skrivesektioner, hvor læsesektionerne kan ombyttes individuelt. Men der tvinges stadigt en rækkefølge, med skiftevis læseblokke, og skriveblokke, og skriveblokkene, skal fungerer, som data skrives i rækkefølge. Dette kan nemt tvinge nødvendighed for sekventiel udførsel ind i sproget. Pointere gør hele hukommelsen, til sekventiel bøvl, da ingen ved, hvor en pointer kan ramme. Hvis man kan spå om, hvor pointeren kan ramme, f.eks. afgrænse det indenfor nogle intervaller - ligesom hvis brugen af indexerbar hukommelse deles over flere arrays, hvor hver array, har sit område, det virker, så kan disse arrays fungere disjunkte, fordi "pointerne" ikke kan ramme i forkerte områder, og dermed opnås også bedre mulighed, for at kunne undgå tvungne rækkefølger. Hvis du laver en grafisk diagram over programmet, som ikke indeholder rækkefølger, så bliver du tvungen til, at anbringe alt hukommelsen i éen blok, der tilgås delvis sekventielt, hvis der bruges pointere, der har et værdiområde på hele hukommelsen. Anvendes ikke pointere, og er eneste brug af hukommelsesblokke i diagrammet, til indexerbar hukommelse (arrays), så kan de arbejde uafhængigt af hindanden, og dermed opnås bedre optimering ved parallelisme.

Så jeg er enig med dig i, at fremtiden sandsynligvis ikke, er et program skrevet i sædvanlig C kode. Problemet ligger i selve måden, som C fungerer, og brugen af pointere, objekter osv. En af mine pointer, er at man sandsynligvis skal undgå brugen af objekter, og programmere parallelt i stedet. OOP, er efter min opfattelse, en "fejl" - det som man ønsker, når man laver et objekt, er normalt en form for parallelisme.

Det er dog intet analytisk problem, i at have sekventiel kode, i et sprog der er egnet til automatisk parallelisering. Sekventiel kode, kan i mange tilfælde, være den mest overskuelige måde, at beskrive en algorithme, og så længe at det beskrives på en analyserbar måde, er det sekventielle i beskrivelsen uproblematisk. Men, hvis der bruges f.eks. pointere, som kan pege på ethvert område, så fungerer det reelt som "overspecificeret" rækkefølge, da der påkræves rækkefølge, mellem brugen af hukommelsen, som ikke er nødvendigt. Og dette kan være svært, at analysere bort.

Jeg tror, at et godt højnivau sprog, skal have andre metoder, at opnå brug af variabel dynamisk hukommelse, end brugen af pointere. Har man brug for en pointer, kan bruges et indexeret array. Derved struktureres brugen af hukommelsen, således data der hører sammen, og kræver sekventiel tilgang, anbringes i samme array, meddens dataklynger, der ikke bør have indflydelse på hinanden, placeres i uafhængige arrays.

Jacob Christian Munch-Andersen

Et program til at løse sudokuer burde ikke fylde mere end 50-150 linjer afhængig af sprog m.m. Så at det tager to timer at skrive det om til at udnytte kernerne (og yderligere et par uger til at optimere det til at udnytte kernerne nogenlunde fornuftigt) lyder bestemt ikke lovende.

Jeg tror i det hele taget ikke meget på ideen om, at man kan tage et allerede skrevet C program og modificere det em smule, så det kører parallelt. Enten skal programmet skrives fra grunden til en bestemt parallel arkitektur, eller det skal skrives i et sprog, der ikke overspecificerer rækkefølge eller datadeling. Og selv da er parallelisering ikke automatisk -- det er blot lettere.


Jeg tænkte omtrent det samme, og det bliver ikke bedre af at sudoku løsning generelt er et af de nemmeste problemer at parallelisere, ingen behov for at dele data mellem tråde, bare lad hver kerne arbejde på sit eget delvise løsningsforslag.

Hvad er i øvrigt en sudoku med 17 tal?
Hvorfor viser skærmen på billedet tilsyneladende almindelige 9x9 sudokuer? (Dem er der da i øvrigt ikke meget sport i når man bruger en computer.)
Og hvorfor er manden på billedet som ser ud som om han forklarer Intels produkt iført hele to styk beklædningsgenstande som antyder at han nok ikke er Intel medarbejder?

Jacob Christian Munch-Andersen

En sudoku med 17 tal er formentlig en af dem her:
http://mapleta.maths.uwa.edu.au/~gordon/sudokumin.php
Dvs en 9x9 med 17 felter allerede udfyldt og som kun har en løsning.
Det er muligt at det program, der omtales, faktisk blot forsøger at søge efter den slags sudokuer?


Tja, sætningen hvor det beskrives hvad programmet rent faktisk gør er noget vrøvl, og da det for en gangs skyld er en artikel hvor V2 selv har været i marken er der ingen hjælp at hente i en velskrevet originalartikel.

Det lyder da som en lidt mere værdig opgave at finde sudoku opgaver, men det er stadig ikke noget som sætter kernernes samarbejdsevner på prøve.

Log ind eller Opret konto for at kommentere