Parallel tests contain different items but have the same measurement properties. They are administered at the same or different time slots and their measurement results must be comparable. The problem of automated parallel tests assembly is studied for a long time, and many (mostly improvement) heuristic solutions are proposed and elaborated in literature. Such approaches frequently suffer from algorithms of unpredictable execution time, forcing the methods to terminate execution when some time limit or solution quality is reached. This paper proposes an efficient method of polynomial complexity, as a complete solution to the automated parallel tests assembly problem. The method uses the idea of Nawaz, Enscore, and Ham constructive heuristic algorithm to reduce the number of examined permutations, originally exploited for solving the permutation flow-shop sequencing problem. We compared the experimental results of the proposed method with two methods based on improvement heuristics that solve the same problem formulation, simulated annealing and variable neighborhood search. The main advantages of the proposed method are predictable execution time and implementation simplicity. Achieved quality of assembled tests, combined with predictable test assembly execution time, may be of particular interest in cases when computational resources for test assembly and administering are overloaded.

Parallel test forms are ubiquitous in the educational, aptitude, achievement, and licensure testing. The problem of automated assembling of parallel test forms has been extensively explored for almost 40 years. Many different mathematical models of the problem formulations and a plenty of different solutions have emerged over the last two decades, indicating that the problem has matured. However, its investigation is still challenging, especially today, when the importance of distance learning and remote knowledge testing is rapidly growing. The diversity of proposed approaches originated notably from the variety of scientific fields involved such as psychometrics, applied mathematics, operations research, and artificial intelligence. Majority of solutions of the problem are (meta)heuristics-based, since they consider the problem as a combinatorial optimization problem which is NP-hard. In this paper, a comprehensive review of this research field, referring to related works since 1985, is conducted. Problem formulations and solutions of the problem are separately classified. Possible avenues of future research are pointed out.

This paper presents our experience with the development of an automated knowledge test assembler. Items are selected from an item bank on the basis of precisely formulated formal criteria. The focus of our research was on the classification of criteria for item selection and on an algorithm that assembles a test using these criteria. The criteria are expressed through parameters of a heuristic function used to evaluate a test’s quality; they were derived from teaching experience and we consider them to be highly intuitive to teachers. Item selection is performed by searching a state space using modified hill-climbing. The proposed quality function is used to guide the search for the optimal test. The test assembler is implemented inside an in-house software system, developed for preparing and scoring of knowledge tests. We have shown a statistically significant improvement in the mean reliability of the tests assembled by our test assembler, compared to the tests assembled by a widely available state-of-the-art tool. The performance indicators of the test assembler were also measured and analyzed. The experiments’ results encourage both practical use of the assembler and further research.

Concentrates on the problem of defining and measuring parameters that characterize typical behavior of parallel applications targeted to distributed shared memory (DSM) systems and shared-memory multiprocessors (SMPs). These parameters can be used as input to various models for performance evaluation in this research area. Furthermore, typical application behaviors can be recognized, which can help to generate new ideas for improvements to memory consistency protocols, adapting them to specific application characteristics. Our study encompasses a variety of parameters, such as frequencies of operations of various access types (private read/writes, shared read/writes, lock operations, barrier operations), the average number of accessed blocks per interval, the average number of modified words, etc. The results presented in this paper are based on the SPLASH-2 (Stanford Parallel Applications for SHared Memory) application suite. The developed instrumentation tool Scowl, along with the applied simulation environment Limes, are publicly available and applicable for performing measurements on other parallel applications as well.

Branch misprediction is one of the important causes of performance degradation in superpipelined and superscalar processors. Most of the existing branch predictors, based on the exploiting of branch history, suffer from prediction accuracy decrease caused by frequent context switches. The goal of this research is to reduce misprediction rate (MPR) when the context switches are frequent, and not to increase the MPR when the context switches are relatively rare. We propose two independent, but closely related modifications of global adaptive prediction mechanisms: first, to flush only the branch history register (BHR) at context switch, instead of reinitialization of the whole predictor, and second, to use two separated BHRs, one for user and one for kernel branches, instead of one global history register. We have evaluated the ideas by measurements on real traces from IBS (Instruction Benchmark Set), and have shown that both modifications reduce MPR at negligible hardware cost.

This survey of heterogeneous computing concepts and systems is based on the recently proposed by the authors "EM/sup 3/ " (Execution Modes/Machine Models) taxonomy of computer systems in general. The taxonomy is based on two criteria: the number of execution modes supported by the system and the number of machine models present in the system. Since these two criteria are orthogonal, four classes exist: Single Execution mode/Single machine Model (SESM), Single Execution modes/Multiple machine Models (SEMM), Multiple Execution modes/Single machine Model (MESM), and Multiple Execution modes/Multiple machine Models (MEMM). In Section II, heterogeneous computing concepts are viewed through three phases of the compilation and execution of any heterogeneous application: parallelism detection, parallelism characterization and resource allocation. Parallelism detection phase discovers fine-grain parallelism inside every task. This phase is not an exclusive feature of heterogeneous computing, so it will not be dealt with in greater detail. The assignment of parallelism characterization phase is to estimate the behavior of each task in the application on every architecture in the heterogeneous system. In the parallelism characterization domain, one original taxonomy is given. This taxonomy contains scheme classes such as vector and matrix static and dynamic, implicit and explicit, algorithmic and heuristic and numeric and symbolic. Resource allocation phase determines the place and the moment for execution of every task to optimize certain performance measure related to some criteria. In the resource allocation domain, the existing Casavant-Kuhl taxonomy is extended and used. This well known taxonomy is supplemented with scheme classes such as noncooperative competitive, noncooperative noncompetitive, and load sharing. In Section III, heterogeneous systems characterized with multiple execution modes ("fully" heterogeneous systems falling in the MESM and the MEMM class) are surveyed. The MESM class systems are described and illustrated with three case studies, two of which support SIMD/MIMD and one supports scalar/vector combination of execution modes. The MEMM class systems are described and illustrated with two representative examples of fully heterogeneous networks supporting multiple execution modes. The system software for heterogeneous computing systems is presented according to an original three-dimensional (3-D) taxonomy whose criteria rely on the level of heterogeneity support implementation, the programming approach, and the data access technique applied. In Section III, several representative heterogeneous applications are described with their computation requirements and the systems used for their execution. Each topic covered in the paper contains several concise examples.