Кіріспе
Параллель алгоритмдерді жобалауға арналған абстрактілі компьютер. Компьютерлік ғылымда параллель кездейсоқ сүйемелдеме машинасы (параллельді RAM немесе PRAM) – ортақ жадқа ие абстрактілі машина. Атауынан көрініп тұрғанындай, PRAM кездейсоқ сүйемелдеме машинасына (RAM) (жедел жадтан шатастырмау керек) параллель есептеудің аналогы ретінде қарастырылады. RAM ретті алгоритмдерді жобалаушылар алгоритмдік өнімділікті (мысалы, уақыт күрделілігін) модельдеу үшін қолданғандай, PRAM параллель алгоритмдерді жобалаушылар параллель алгоритмдік өнімділікті (мысалы, уақыт күрделілігін, онда процессорлардың саны да әдетте көрсетіледі) модельдеу үшін қолданады. RAM моделі практикалық мәселелерді, мысалы, кэш жадына және негізгі жадқа қол жеткізу уақытын ескермейтіндей, PRAM моделі де синхрондау және байланыс сияқты мәселелерді ескермейді, бірақ кез келген (мәселенің көлеміне байланысты) процессорлар санын ұсынады. Алгоритмнің құны, мысалы, екі параметр арқылы бағаланады: O(уақыт) және O(уақыт × процессорлар саны).
In computer science, a parallel random access machine (parallel RAM or PRAM) is a shared memory abstract machine. As its name indicates, the PRAM is intended as the parallel computing analogy to the random access machine (RAM) (not to be confused with random access memory). In the same way that the RAM is used by sequential algorithm designers to model algorithmic performance (such as time complexity), the PRAM is used by parallel algorithm designers to model parallel algorithmic performance (such as time complexity, where the number of processors assumed is typically also stated). Similar to the way in which the RAM model neglects practical issues, such as access time to cache memory versus main memory, the PRAM model neglects such issues as synchronization and communication, but provides any (problem size dependent) number of processors. Algorithm cost, for instance, is estimated using two parameters O(time) and O(time × processor number).
Іске асыру
PRAM алгоритмдерін CPU және динамикалық кездейсоқ кіру жады (DRAM) комбинациясымен параллельдеу мүмкін емес, себебі DRAM бір банкке бір уақытта қол жеткізуге рұқсат бермейді (банк ішіндегі әртүрлі адрестерге де емес); бірақ оларды аппараттық құралда жүзеге асыруға болады немесе FPGA (Field Programmable Gate Array) ішкі статикалық кездейсоқ кіру жады (SRAM) блоктарына оқу/жазу арқылы іске қосуға болады, бұл CRCW алгоритмін пайдалану арқылы жасалуы мүмкін. Дегенмен, PRAM (немесе RAM) алгоритмдерінің практикалық маңыздылығын бағалау олардың құн моделінің қандай да бір компьютердің тиімді абстракциясын ұсынуына байланысты; осы компьютердің құрылымы абстрактілі модельден өте ерекше болуы мүмкін. Қабаттардың бағдарламалық және аппараттық деңгейдегі құрылымын білу осы мақаланың шегінен тыс. Бірақ, PRAM сияқты абстракцияны нақты көп жіптілік (XMT) парадигмасымен қалай қолдауға болатынын көрсететін мақалалар бар, сондай-ақ PRAM алгоритмі максималды ағын мәселесі үшін сол мәселенің ең жылдам тізбектік бағдарламасына қарағанда айтарлықтай жылдамдыққа қол жеткізе алатынын көрсететін мақалалар да бар. Мақалада PRAM алгоритмдері XMT-де көп жіпті бағдарлама ретінде оларды өзгертуге қосымша күш жұмсамай-ақ, бәсекеге қабілетті өнімділікке қол жеткізе алатыны көрсетілген.