What is Parallel Random-Access Machine (PRAM)

This chapter deals with the process of formalized design of sequential and parallel algorithms based on algorithm algebras. It gives the main concepts associated with metarules of schemes design (convolution, involution, reinterpretation, transformation). The SAA/1 language focused on natural linguistic algorithm representation and based on Glushkov's algebras is described. The algebra-grammatical models for parameter-driven generation of algorithm specifications based on higher-level schemes (hyperschemes) are then constructed. The authors propose the extension of the well-known PRAM model that is the basis of program auto-tuning. The hyperschemes and the auto-tuning are the means of increasing the adaptability of algorithms and programs to specific conditions of their use (for example, target computing platform). Some examples of formalized design of parallel sorting algorithm schemes using operations of Glushkov's algebras are given.