In this paper, a platform is presented, that given a Stochastic Context-Free Grammar (SCFG), automatically outputs the description of a parser in synthesizable Hardware Description Language (HDL) which can be downloaded in an FPGA (Field Programmable Gate Arrays) board. Although the proposed methodology can be used for various inexact models, the probabilistic model is analyzed in detail and the extension to other inexact schemes is described. Context-Free Grammars (CFG) are augmented with attributes which represent the probability values. Initially, a methodology is proposed based on the fact that the probabilities can be evaluated concurrently with the parsing during the parse table construction by extending the fundamental parsing operation proposed by Chiang & Fu. Using this extended operation, an efficient architecture is presented based on Earley’s parallel algorithm, which given an input string, generates the parse table while evaluating concurrently the probabilities of the generated dotted grammar rules in the table. Based on this architecture, a platform has been implemented that automatically generates the hardware design of the parser given a SCFG. The platform is suitable for embedded systems applications where a natural language interface is required or in pattern recognition tasks. The proposed hardware platform has been tested for various SCFGs and was compared with previously presented hardware parser for SCFGs based on Earley’s parallel algorithm. The hardware generated by the proposed platform is much less complicated than the one of comparison and succeeds a speed-up of one order of magnitude.

In this paper a parallel algorithm for branch and bound applications is proposed. The algorithm is a general purpose one and it can be used to parallelize effortlessly any sequential branch and bound style algorithm, that is written in a certain format. It is a distributed dynamic scheduling algorithm, i.e. each node schedules the load of its cores, it can be used with different programming platforms and architectures and is a hybrid algorithm (OpenMP, MPI). To prove its validity and efficiency the proposed algorithm has been implemented and tested with numerous examples in this paper that are described in detail. A speed-up of about 9 has been achieved for the tested examples, for a cluster of three nodes with four cores each.

In this paper a platform is presented, that given a stochastic context-free grammar (SCFG), automatically outputs the description of the parser in synthesizable hardware description language (HDL) which can be downloaded in an Field Programmable Gate Arrays (FPGA) board. Initially, according to our methodology the SCFG is augmented with attributes which store the probability values and can be evaluated through corresponding stack actions. The architecture of the produced system is based on a proposed extension of Earley’s parallel algorithm, which given an input string, generates the parse trees in the form of an AND-Or parse tree. This AND-or parse tree is then traversed using a proposed tree traversal technique in order to execute the corresponding actions in the correct order, so as to compute the necessary probabilities. The platform is suitable for embedded systems applications where a natural language interface is required or in pattern recognition tasks. The parser generated by the presented platform has been tested for various SCFGs and compared to software approaches. The performance comparison is one to two orders of magnitude in favor of the presented hardware, compared to previous software approaches, depending on the application, the input string length and the number of produced trees.

SUMMARY Loops are the richest source of parallelism in scientific applications. A large number of loop scheduling schemes have therefore been devised for loops with and without data dependencies (modeled as dependence distance vectors) on heterogeneous clusters. The loops with data dependencies require synchronization via cross‐node communication. Synchronization requires fine‐tuning to overcome the communication overhead and to yield the best possible overall performance. In this paper, a theoretical model is presented to determine the granularity of synchronization that minimizes the parallel execution time of loops with data dependencies when these are parallelized on heterogeneous systems using dynamic self‐scheduling algorithms. New formulas are proposed for estimating the total number of scheduling steps when a threshold for the minimum work assigned to a processor is assumed. The proposed model uses these formulas to determine the synchronization granularity that minimizes the estimated parallel execution time. The accuracy of the proposed model is verified and validated via extensive experiments on a heterogeneous computing system. The results show that the theoretically optimal synchronization granularity, as determined by the proposed model, is very close to the experimentally observed optimal synchronization granularity, with no deviation in the best case, and within 38.4% in the worst case. Copyright © 2012 John Wiley & Sons, Ltd.

In this paper we give a theoretical model for determining the synchronization frequency that minimizes the parallel execution time of loops with uniform dependencies dynamically scheduled on heterogeneous systems. Using this model we determine the synchronization frequency that minimizes the estimated parallel time. The accuracy of our method is validated through experiments on a heterogeneous cluster. The results show that the synchronization frequency minimizing the parallel time determined by our method, is very close to the synchronization frequency found experimentally.

This paper addresses dynamic load balancing algorithms for non-dedicated heterogeneous clusters of workstations. We propose an algorithm called self-adapting scheduling (SAS), targeted at nested loops with dependencies in a stochastic environment. This means that the load entering the system, not belonging to the parallel application under execution, follows an unpredictable pattern which can be modeled by a stochastic process. SAS takes into account the history of previous timing results and the load patterns in order to make accurate load balancing predictions. We study the performance of SAS in comparison with DTSS. We established in previous work that DTSS is the most efficient self-scheduling algorithm for loops with dependencies on heterogeneous clusters. We test our algorithm under the assumption that the interarrival times and life-times of incoming jobs are exponentially distributed. The experimental results show that SAS significantly outperforms DTSS especially with rapidly varying loads

In this work, a novel heuristic algorithm for the minimization of Exclusive-Or Sum Of Products (ESOP) expressions for multiple output incompletely specified functions is presented. An initial algorithm, DCMIN, uses functional decomposition and multiple-valued logic in order to produce almost minimal expressions for these functions. Based on DCMIN, an improved algorithm, QuickDCMIN, is proposed, which outperforms existing algorithms.

Distributed computing systems are a viable and less expensive alternative to parallel computers. However, concurrent programming methods in distributed systems have not been studied as extensively as for parallel computers. Some of the main research issues are how to deal with scheduling and load balancing of such a system, which may consist of heterogeneous computers. In the past, a variety of dynamic scheduling schemes suitable for parallel loops (with independent iterations) on heterogeneous computer clusters have been obtained and studied. However, no study of dynamic schemes for loops with iteration dependencies has been reported so far. In this work we study the problem of scheduling loops with iteration dependencies for heterogeneous (dedicated and non-dedicated) clusters. The presence of iteration dependencies incurs an extra degree of difficulty and makes the development of such schemes quite a challenge. We extend three well known dynamic schemes (CSS, TSS and DTSS) by introducing synchronization points at certain intervals so that processors compute in pipelined fashion. Our scheme is called dynamic multi-phase scheduling (DMPS) and we apply it to loops with iteration dependencies. We implemented our new scheme on a network of heterogeneous computers and studied its performance. Through extensive testing on two real-life applications (the heat equation and the Floyd-Steinberg algorithm), we show that the proposed method is efficient for parallelizing nested loops with dependencies on heterogeneous systems.

This paper deals with general nested loops and proposes a novel scheduling methodology for reducing the communication cost of parallel programs. General loops contain complex loop bodies (consisting of arbitrary program statements, such as assignments, conditions and repetitions) that exhibit uniform loop-carried dependencies. Therefore it is now possible to achieve efficient parallelization for a vast class of loops, mostly found in DSP, PDEs, signal and video coding. We use computational geometry methods, that exploit efficiently the regularity of nested loops index spaces, in order to significantly reduce the communication cost, which in most cases is the main drawback of parallel programs' performance. Through extensive testing, we show that the proposed method outperforms in all cases the classic cyclic mapping, succeeding to reduce the communication by 15%-35%. This significant reduction of the communication volume makes our method a promising candidate to be incorporated into existing automatic parallel code generation tools

This work presents theoretical results and an efficient heuristic algorithm for minimizing single - output exclusive - or sum-of-products expressions, based on an iterative product term transformation paradigm. Experimental results verify the efficiency of the algorithm in terms of execution times and product term count of the produced expression, when compared to a state-of-the-art heuristic ESOP minimizer for single-output benchmark and randomly generated functions.

In this article, the self-organizing map (SOM) is employed to analyze data describing the 24-hour blood pressure and heart-rate variability of human subjects. The number of observations varies widely over different subjects, and therefore a direct statistical analysis of the data is not feasible without extensive pre-processing and interpolation for normalization purposes. The SOM network operates directly on the data set, without any pre-processing, determines several important data set characteristics, and allows their visualization on a two-dimensional plot. The SOM results are very similar to those obtained using classic statistical methods, indicating the effectiveness of the SOM method in accurately extracting the main characteristics from the data set and displaying them in a readily understandable manner. In this article, the relation is studied between the representation of each subject on the SOM, and his blood pressure and pulse-rate measurements. Finally, some indications are included regarding how the SOM can be used by the medical community to assist in diagnosis tasks. © 2002 John Wiley & Sons, Inc.

Having to cope with the continuously increasing complexity of modern digital systems, hardware designers are considering more and more seriously language based methodologies for parts of their designs. Last year the introduction of a new language for hardware descriptions, the SystemC C++ class library, initiated a closer relationship between software and hardware descriptions and development tools. This paper presents a synthesis environment and the corresponding synthesis methodology, based on traditional compiler generation techniques, which incorporate SystemC, VHDL and Verilog to transform existing algorithmic software models into hardware system implementations. Following this approach, reusability of software components is introduced in the hardware world and time-to-market is decreased, as shown by experimental results.

The adoption of hardware description languages as a design specification formalism, in the electronic design automation industry, has reached acceptance during the last years. This effort has been mainly supported by the VHDL and Verilog standardization activities, which are now offering a common formalism among different tool vendors, as well as novel ideas like the SystemCC++ class library, which promises hardware modeling using C++ syntax and a higher level of specification abstraction. The broad range of modern description language spectrum, supports efficient language based synthesis processes, starting at even higher abstraction levels. This paper presents a language based design environment, which combines synthesis and formal verification tasks, using an advanced compiler generator and based on language transformations. This combination, presenting low complexity, offers more power to language based synthesis and design management and can be used to find errors and better understand issues of behavioral modeling.

One of the primary tasks in the area of uniform dependence loops, is predicting the execution propagation, as well as finding an optimal time schedule. In this work, the problem of scheduling using wavefront prediction is presented. The geometric concepts of time instance subspaces and execution pattern are introduced. A quite simple and low complexity scheduling algorithm is presented. The index space is split into geometric subspaces and any point can be located in them. Each point is then scheduled according to the subspace where it belongs.

This paper compares three similar loop-grouping methods. All methods are based on projecting the n-dimensional iteration space J/sup n/ onto a k-dimensional one, called the projected space, using (n-k) linear independent vectors. The dimension k is selected differently in each method giving various results. The projected space is divided into discrete groups of related iterations, which are assigned to different processors. Two of the methods preserve optimal time completion, by scheduling loop iterations according to the hyperplane method. The theoretical analysis of the experimental results indicates the appropriate method, for specific iteration spaces and target architectures.

This paper presents Chain Grouping, a new low complexity method for the problem of partitioning the loop iteration space into groups with little intercommunication requirements, for mapping onto mesh-connected architectures. First, the iterations are scheduled in time, according to the hyperplane method, taking into consideration the minimum time displacement. Then, the iteration space is divided into discrete groups of related iterations, which are assigned to different processors, while preserving the optimal completion time. Chain Grouping is based on clustering together neighboring uniform chains of iterations, formed by a particular dependence vector. This vector will be proven as the best among all to reduce the total communication requirements. Inside every group, the optimal hyperplane scheduling is preserved and references to intragroup iterations are considerably increased. The partitioned groups are afterward assigned to meshes of processors. The resulting space mapping maximizes processor utilization and cuts down overall communication delays while preserving the optimal hyperplane time schedule.

Attribute grammars have been used extensively in every phase of traditional compiler construction. Recently, it has been shown that they can also be effectively adopted to handle scheduling algorithms in high-level synthesis. Their main advantages are modularity and declarative notation in the development of design automation environments. In this paper, past results are further elaborated and more scheduling techniques are presented and implemented in a flexible environment for the design automation of digital systems. This novel approach can be proven valuable for fast evaluation of new algorithms and techniques in the field.

We propose a fixed size one dimensional VLSI architecture for the parallel parsing of arbitrary context free (CF) grammars, based on Earley's algorithm. The algorithm is transformed into an equivalent double nested loop with loop carried dependencies. We first map the algorithm into a 1D array with unbounded number of cells. The time complexity of this architecture is O(n), which is optimal. We next propose the partitioning into a fixed number of off the shelf processing elements. Two alternative partitioning strategies are presented considering restrictions, not only in the number of the cells, but also in the inner structure of each cell. In the most restricted case, the proposed architecture has time complexity O(n/sup 3//p*k), where p is the number of available cells and the elements inside each cell are at most k.

In order to localize itself a mobile robot tries to match its sensory information at any instant against a prior environment model, the map. A probabilistic map can be regarded as a model that stores at each robot configuration q the probability density function of the sensor readings at q. By combining the knowledge of its current position, the new-coming sensory information, and the probabilistic map the robot is capable of improving its prior position estimate. In this paper we propose a novel sensor model and a method for maintaining a probabilistic map in cases of dynamic environments. When the environment structure changes, the map must adapt to this change by modifying the sensor densities, at the respective configurations. We propose a combined algorithm for map update and robot localization.

The paper presents Chain grouping; a new low complexity method for the problem of partitioning the index space into groups with little intercommunication requirements, for mapping onto distributed mesh connected architectures. First the loop iterations are scheduled in time, according to the hyperplane method, taking into consideration the minimum time displacement. Then, the index space is divided into discrete groups of related computations, which are assigned to different processors, while preserving the optimal makespan. The Chain grouping method is based on grouping along a uniform chain of computations, formed by a particular dependence vector. This vector will be proved as the best to reduce the total communication requirements. Inside every group, the optimal hyperplane scheduling is preserved, and the references to intragroup computations are considerably increased. The partitioned groups are afterwards assigned to meshes of processors. The resulting space mapping maximises processor utilisation and cuts down overall communication delays while preserving the optimal hyperplane time schedule.

Since natural language parsing is a computationally intensive task, the parallel parsing of natural language seems a promising choice. This paper describes both the Eu-PAGE (Eurotra PArser GEnerator) meta-compiler for the Eurotra formalism, which is a tool that automatically generates parallel natural language parsers, and the Dialogos parser, which is a parallel parser for the Greek language generated by Eu-PAGE. Parallel parsers generated by Eu-PAGE are based on finite-state machines, employ coarse-grained parallelism and are portably implemented on top of two parallel software platforms: PVM and Orchid. Orchid uses light-weight processes as the basic unit of parallelism, enhanced with advanced operating system facilities. The collected experimental results so far demonstrate satisfactory speed-ups of the parallel implementations compared to the sequential one.

We describe a novel dynamic dramatization method for narrative presentations. This method accepts as input the original story material, along with a description of its plot written in a special-purpose language. It then analyzes the plot to identify interesting dramatic situations in the story. Based on this content analysis, a presentation manager organizes the presentation and enriches it with appropriate multimedia effects. These effects are associated with interesting dramatic situations, and serve to increase suspense and emphasize plot developments in the narrative. Our method can be used for the development of intelligent front-ends to story databases, for directing assistants in computer-based renditions of narrative works, or for real-time direction of interactive entertainment systems. We are integrating this system in an interactive storytelling environment for Greek mythology.

We describe a novel architecture for indoor navigation, based on qualitative representations of the variations in the interactions between the robot and its environment. We use these representations to localize and guide planning and reaction. The system accepts off-line as input a topological diagram of the environment. It then uses numerical simulation to generate a map, describing qualitative variations in the sensor behavior between adjacent regions in space. An off-line planner stores localized navigation information at each point in the map. During execution, an adaptive controller uses a short-term memory to improve its operation. The qualitative nature of our method, along with the localization performed by the topological planner result in a compact map representation and in linear-time performances for position estimation and path planning during execution. This architecture has been tested in simulation. Our results show that the proposed navigation method is tolerant of sensor inaccuracies, both in obstacle detection and orientation.

We describe a novel global path planning method for autonomous qualitative navigation in indoor environments. Global path planning operates on top of a qualitative map of the environment that describes variations in sensor behavior between adjacent regions in space. The method takes into consideration the global topology of the environment and applies a set of criteria that can minimize the errors in the navigational accuracy of a robotic wheelchair. Our approach uses a modified version of the Dijkstra's shortest path algorithm that takes into consideration the curvature of the trajectory and the off-wall distance of the map points. The algorithm computes in real-time a set of optimal paths for reaching the destination. We have tested our global path planning method in simulation in representative indoor environments with above average complexity. Based on these experiments we have determined empirically a set of values for the parameters of the algorithm that almost always lead to the selection of optimal paths in these environments.

The most important issue when parallelizing sequential programs is the efficient assignment of computations into different processing elements. The most extensive, in terms of time execution, part of a program is the nested loops. Too many approaches have been devoted in parallelizing nested loops, and assigning the concurrent partitions of such a loop into different processors. In the past, all methods have been focused upon linear schedules produced by manipulating the reduced dependence graph, which in some cases achieve near optimal solutions. This paper presents a new method of free scheduling loop computations into time, based on task graph scheduling techniques. It will be shown that this schedule is optimal in terms of time, outperforming all linear schedules. Furthermore, in terms of total number of processors, the presented method includes a heuristic refinement of the free schedule which ‘shuffles’ computations into time, without loss of the optimal time performance, to augment the mean processor utilization. In all cases, the proposed method uses less number of processors, while preserving the optimal total execution time. The ‘shuffling’ of computations is based on graph theory approaches, and uses PERT problem techniques. Such scheduling is convenient for parallelizing tools (such as compilers), but has practical interest for shared memory multiprocessor systems, where the communication delay imposed by such non-regular scheduling is of no interest.

As knowledge-based techniques are introduced in supervision and control applications, the need for a structured, methodological approach in the development of these systems increases. Current knowledge-based systems development methodologies are founded on individualistic models of expertise, and cannot face the challenge of interacting with humans or other systems in dynamic application environments. This article introduces a development method that combines models of expertise with interaction-based distributed artificial intelligence. The applicability of the method is demonstrated on an example of supervision of a power transmission network. The analysis of the proposed system is based on the KADS methodology. The design phase is structured in a series of steps: first, the domain description is used to select a model of distributed problem solving. Then, problem constraints and a set of design rules guide the mapping of the analysis' entities to a design solution. Design decisions are justified at every step. Alternative design proposals are experimentally compared with the aid of a multi-agent platform and a simulator. The experimental results indicate possible design refinements. Finally, the generality of the approach is discussed and future research directions are indicated.>

A methodology based on functional programming for the systematic synthesis of problem-oriented architectures is presented. The different ways of sequencing the input data are shown to lead to a variety of alternative architectures for the same computational problem (with the same behavioural description). The finally selected architecture satisfies certain user-defined restrictions and maximises given performance criteria. The presented methodology is applicable to a wide range of computing problems and can be used in the process of designing specialised VLSI systems.

The use of attribute grammars for knowledge representation is examined in the present paper. It is shown how data knowledge and knowledge-base knowledge can be represented using syntactic and semantic notation. Control knowledge is represented by the parsing mechanism of the interpreter used. It is proposed that attribute grammar evaluators may prove to be useful knowledge engineering tools.

It is shown that the general case of optimal evaluation of Boolean expression queries, with different cost and truth probabilities for the different variables and without the uniqueness restriction, is a special case of finding the optimal decision tree of a limited entry decision table.

A new program control structure is proposed in this paper which is suitable for expressing a variable number of nested loops. This control structure is useful in combinatorial problems and in problems requiring backtracking. Implementation details are discussed and some illustrative examples are given which employ this new program control structure. The incorporation of this control structure in contemporary programming languages will considerably enhance them, particularly languages like FORTRAN, BASIC, and assembly.

A syntax-directed interpreter of attribute grammars is applied to interpret meta grammars describing translators. A specific example is used which concerns the formal description of the same syntax-directed interpreter of attribute grammars for illustration of our approach.

A simple portable interpreter for testing the specifications of problems is presented in this paper. These specificiations are supposed to be expressed in the formalism of attribute grammars. The parsing and the semantics evaluation are carried out simultaneously, so that the parsing can be directed by the semantics. This increases the power of the grammars and context sensitive characteristics of a language can be described.

Abstract An approach is described in this paper for realizing attribute grammars. A system called STAR has been implemented according to this approach. The system is based on the STAGE2 macroprocessor. It is simple, portable, it can run even on small machines, it can be quickly implemented and it has a convenient to the user metalanguage. The system, however, disregards efficiency and is limited to small size problems.

This correspondence attempts to solve the problem of expressing an arbitrary switching function in a modulo-2 sum-of-product terms form, having a minimum number of product terms. Each product term may contain variables in complemented or uncomplemented form.

A method is described to generate all prime cascades of the restricted Maitra type with fixed input order, of an arbitrary switching function. The method allows the optimal synthesis of cutpoint cellular arrays.

The method described in [1] for transforming a cascade with the standard cell-index set to an equivalent cascade with any complete cell-index set is generalized for transforming a cascade with an arbitrary cell-index set to an equivalent one with another arbitrary cell-index set.

In the present paper three theorems are developed to merge two columns in a cutpoint cellular array into one, depending on the sequence of cutpoint indices in each of the columns. An algorithm is then proposed for realizing arbitrary switching functions with a cutpoint cellular array, based on a set of rules derived from the above theorems. The algorithm is tested with numerous examples.

A computer control system simulation method utilizing two computers is presented. One is a control computer operating under almost actual conditions. The other is a multiprogrammed computer that simulates the plant. The time taken by the control computer to compute the control variables can be a function of the plant state. An optimum control example illustrating the application of the method is given.