Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Параллель алгоритмдерде тізімді реттеу мәселесі байланысты тізімдегі әрбір элементтің орнын немесе орнын анықтауды қамтиды. Яғни, тізімдегі бірінші элементке 1-ші нөмірді, ал екінші элементке 2-ші нөмірді және т.б. беру керек. Бұл мәселені тізбекті компьютерде тиімді шешу оңай болса да, тізімді ретпен өту арқылы, оны қатар шешу күрделірек. Жазғандай, бұл мәселе параллель алгоритмдер қауымдастығында оның көптеген қолданбалары үшін де, оны шешу параллель алгоритмдерде жалпы қолданылуы мүмкін көптеген маңызды идеяларға әкелгендіктен де маңызды деп саналды.
In parallel algorithms, the list ranking problem involves determining the position, or rank, of each item in a linked list. That is, the first item in the list should be assigned the number 1, the second item in the list should be assigned the number 2, etc. Although it is straightforward to solve this problem efficiently on a sequential computer, by traversing the list in order, it is more complicated to solve in parallel. As wrote, the problem was viewed as important in the parallel algorithms community both for its many applications and because solving it led to many important ideas that could be applied in parallel algorithms more generally.
Тарих
Тізімді реттеу мәселесін Лори К. Л. Л. , логарифмдік уақыт пен O ((n log n) жалпы қадамдарды (яғни O ((n) процессорларды) пайдалана отырып, оны параллель алгоритммен шешті. Көптеген кейінгі мақалалар тізбектілігі бойынша, бұл, ақыр соңында, сызықтық көп қадамдық (O ((n / log n) процессорларға), синхронды ортақ жад параллельді есептеудің ең шектеуші моделіне, эксклюзивті оқу эксклюзивті жазу PRAM (; ;) -ға жақсартылды. Бұл қадамдар саны реттілік алгоритмімен сәйкес келеді.
The list ranking problem was posed by , who solved it with a parallel algorithm using logarithmic time and O(n log n) total steps (that is, O(n) processors). Over a sequence of many subsequent papers, this was eventually improved to linearly many steps (O(n/log n) processors), on the most restrictive model of synchronous shared memory parallel computation, the exclusive read exclusive write PRAM (; ;). This number of steps matches the sequential algorithm.
Қатысушы мәселелер
Тізімді реттілікпен қатар, берілген тізімде префикс қосындысы операциясы орындалады деп қарастыруға болады, онда қосындыланатын мәндердің барлығы бірге тең. Тізімдік реттілік мәселесі ағаштардағы көптеген мәселелерді Эйлер тур техникасы арқылы шешу үшін пайдаланылуы мүмкін, онда ағаштың әр жиегінің екі көшірмесін қамтитын, әр бағыттағы бірі, осы тізімнің түйіндерін тізімдік реттілікті пайдалана отырып, реттелген массивке орналастырады, содан кейін реттелген массивте префикс жиынтығын есептеуді орындайды. Мысалы, ағаштағы әрбір түйіннің биіктігі осы типтегі алгоритммен есептелуі мүмкін, онда префикс жиынтығы әр төменгі жиеге 1 қосылады және әр жоғары жиеге 1 алынады.
List ranking can equivalently be viewed as performing a prefix sum operation on the given list, in which the values to be summed are all equal to one. The list ranking problem can be used to solve many problems on trees via an Euler tour technique, in which one forms a linked list that includes two copies of each edge of the tree, one in each direction, places the nodes of this list into an ordered array using list ranking, and then performs prefix sum computations on the ordered array For instance, the height of each node in the tree may be computed by an algorithm of this type in which the prefix sum adds 1 for each downward edge and subtracts 1 for each upward edge.