sprzęt vs. programista

Moore's law

Prawo Moore'a (źródło: Wikipedia)

Prawo Moore’a mówi, że moc obliczeniowa komputerów podwaja się co dwa lata. My, programiści, powinniśmy się z tego cieszyć, ponieważ teoretycznie oznacza to, że możemy sobie pozwalać na coraz więcej w tworzonych aplikacjach. Wszakże maszyna i tak to policzy, jeżeli za wolno – cóż, na pudełku naklei się nalepkę o wyższych wymaganiach sprzętowych (vide pewna gra).

Prawo Moore’a nie zwalnia jednak z myślenia. Nie bez przyczyny wymyślono dziedzinę „Algorytmy i struktury danych”. Aby nie być gołosłownym – przykład z życia wzięty:

Projekt: symulator frezowania. Aplikacja ma wyświetlać na trójwymiarowej scenie blok materiału (15cm x 15cm x 5cm) z dokładnością 0.1 mm i umożliwiać przeprowadzanie symulacji ruchu narzędzia, które poruszając się po pewnej ścieżce usuwa z bloku materiał. Jak nietrudno zauważyć, aby osiągnąć wymaganą dokładność, należy zbudować siatkę 1500 x 1500 punktów, na podstawie tej siatki zbudować trójkąty, a następnie je wyświetlić.

Prosta zagadka matematyczna – ile trójkątów należy wyświetlić w każdej klatce? 1500 * 1500 * 2 (trójkąty na quad) = 4,5 mln trójkątów. W trybie wyświetlania siatkowego nie jest jeszcze tak źle – 50 FPS, jednak przy próbie przejścia do wypełniania trójkątów i obliczania oświetlenia moja karta graficzna kuli się w kącie, zaczyna ssać kciuk i wypluwa z siebie 2-3 klatki na sekundę. Nie można obarczyć za to winą zastosowanych technologii – Microsoftowe XNA jest z powodzeniem wykorzystywane do pisania gier (czyli najbardziej wymagających aplikacji), natomiast obliczaniem oświetlenia zajmuje się procesor karty graficznej – jednostka właśnie do tego stworzona.

Rozwiązanie tego problemu jest trywialne i zostało już w tym poście wymienione. Tu właśnie wkraczają struktury danych. Siatkę należy zamienić na drzewo czwórkowe. Liczby mówią same za siebie:

  • w przypadku użycia siatki w każdej klatce do narysowania jest stała ilość 4,5 mln trójkątów
  • w przypadku użycia drzewa czwórkowego ilość trójkątów do narysowania zmienia się od 2 (płaski blok materiału) do około 100 tys (duży stopień szczegółowości modelu)

Nowa karta graficzna: 1000 PLN, 90% mniej prymitywów graficznych do narysowania – bezcenne. A wszystko sponsorują właściwie użyte algorytmy i struktury danych.

sprzęt vs. programista 0 : 1

Be Sociable, Share!
czoper opublikowano dnia 2009-11-17 Kategoria: Programowanie | Tagi:, ,

Zostaw odpowiedź

(Ctrl + Enter)