共查询到20条相似文献,搜索用时 23 毫秒
1.
Earley's algorithm has been commonly used for the parsing of general context-free languages and the error-correcting parsing in syntactic pattern recognition. The time complexity for parsing is 0(n3). This paper presents a parallel Earley's recognition algorithm in terms of an ``X*' operator. By restricting the input context-free grammar to be ?-free, the parallel algorithm can be executed on a triangular-shape VLSI array. This array system has an efficient way of moving data to the right place at the right time. Simulation results show that this system can recognize a string with length n in 2n + 1 system time. We also present a parallel parse-extraction algorithm, a complete parsing algorithm, and an error-correcting recognition algorithm. The parallel complete parsing algorithm has been simulated on a processor array which is similar to the triangular VLSI array. For an input string of length n the processor array will give the correct right-parse at system time 2n + 1 if the string is accepted. The error-correcting recognition algorithm has also been simulated on a triangular VLSI array. This array recognizes an erroneous string of length n in time 2n + 1 and gives the correct error count. These parallel algorithms are especially useful for syntactic pattern recognition. 相似文献
2.
Two new isometric array languages, called Linear Array Languages (LAL) and Extended Regular Array Languages (ERAL), are introduced. A more abundant hierarchy for isometric languages is established. We show that some properties of two-dimensional array patterns do not coincide with their one-dimensional counterparts. 相似文献
3.
Jonas Barklund 《New Generation Computing》1994,12(2):161-182
The only means for repetition in most logic programming languages, including Prolog, is recursion. Definite iteration is introduced
in logic programming languages through the bounded quantification construct. Firstly, it is claimed that this construct is
often, though not always, more natural than recursion for expressing relations that involve repetition. In particular, programs
involving arrays and similar data structures are significantly simplified. Secondly, it is argued that bounded quantifications
should be efficiently implementable on sequential computers and have a high potential for running in parallel, particularly
on computers supporting the SPMD model of computation.
Bounded quantifications are compared with related constructs from other languages, including the definite loops of imperative
languages and the array comprehensions of recent functional languages. 相似文献
4.
Dynamical consistency in hierarchical supervisory control 总被引:1,自引:0,他引:1
A hierarchical control theory is presented founded upon the trace-dynamical consistency property, which is an extension of the notion of dynamical consistency (DC) to the supervisory case of automata with disablable transitions. Partitions of a system state space are considered for which both the trace-DC and the (non-blocking) in-block controllability (IBC) conditions hold; it is shown that low-level non-blocking controllable languages project up to such languages in the high-level system, and that, when the (non-blocking) IBC condition also holds, high-level non-blocking controllable languages map down to such languages in the low-level system. It is demonstrated that the resulting pairs of low-level and high-level languages satisfy a version of the hierarchical consistency condition found in the existing language-based hierarchical supervisory control theory. The structures produced in the formulation of hierarchical control in this paper permit efficient regulator design (and, in particular, repeated re-design) for hierarchy-compatible language specifications; such specifications consist of low-level languages whose maximal controllable sublanguages are realizable by a combination of a high-level (possibly history-dependent) regulator and a set of (state-dependent) low-level regulators (specified block-wise). An algorithm is proposed which facilitates the construction of (non-blocking) IBC partitions of systems with vocalized states. Examples are presented, including a material transfer line with re-entrant flow and a double queue 相似文献
5.
Regular languages (RL) are the simplest family in Chomsky’s hierarchy. Thanks to their simplicity they enjoy various nice algebraic and logic properties that have been successfully exploited in many application fields. Practically all of their related problems are decidable, so that they support automatic verification algorithms. Also, they can be recognized in real-time.Context-free languages (CFL) are another major family well-suited to formalize programming, natural, and many other classes of languages; their increased generative power w.r.t. RL, however, causes the loss of several closure properties and of the decidability of important problems; furthermore they need complex parsing algorithms. Thus, various subclasses thereof have been defined with different goals, spanning from efficient, deterministic parsing to closure properties, logic characterization and automatic verification techniques.Among CFL subclasses, so-called structured ones, i.e., those where the typical tree-structure is visible in the sentences, exhibit many of the algebraic and logic properties of RL, whereas deterministic CFL have been thoroughly exploited in compiler construction and other application fields.After surveying and comparing the main properties of those various language families, we go back to operator precedence languages (OPL), an old family through which R. Floyd pioneered deterministic parsing, and we show that they offer unexpected properties in two fields so far investigated in totally independent ways: they enable parsing parallelization in a more effective way than traditional sequential parsers, and exhibit the same algebraic and logic properties so far obtained only for less expressive language families. 相似文献
6.
《International Journal of Parallel, Emergent and Distributed Systems》2012,27(1-3):21-56
Data flow analysis has been used by compilers in diverse contexts, from optimization to register allocation. Traditional analysis of sequential programs has centered on scalar variables. More recently, several researchers have investigated analysis of array sections for optimizations on modern architectures. This information has been used to distribute data, optimize data movement and vectorize or parallelize programs. As multiprocessors become more common-place. we believe there will be considerable interest in explicitly parallel programming languages. In this paper, we extend traditional analysis to array section analysis for parallel languages which include additional control and synchronization structures. We show how to compute array section data flow information, i.e., Communication Sets, for a class of parallel programs. To illustrate its use, we show how this information can be applied in compile-time program partitioning. Information about array accesses can also be used to improve estimates of program execution time used to direct runtime thread scheduling. 相似文献
7.
There are many paradigms being promoted and explored for programming parallel computers, including modified sequential languages,
new imperative languages and applicative languages. SISAL is an applicative language which has been designed by a consortium
of industrial and research organizations for the specification and execution of parallel programs. It allows programs to be
written with little concern for the structure of the underlying machine, thus the programmer is free to explore different
ways of expressing the parallelism. A major problem with applicative languages has been their poor efficiency at handling
large data structures. To counter this problem SISAL includes some advanced memory management techniques for reducing the
amount of data copying that occurs. In this paper we discuss the implementation of some image processing benchmarks in SISAL
and C to evaluate the effectiveness of the memory management code. In general, the SISAL program was easier to code than the
C (augmented with the PARMACS macros) because we were not concerned with the parallel implementation details. We found that
the SISAL performance was in general comparable to C, and that it could be brought in line with an efficient parallel C implementation
by some programmer-specified code transformations. 相似文献
8.
This paper presents the applicability of graph L-systems to the generation of two-dimensional pictures. It is shown that the class of graphs generated by extended tabled node-replacement graph L-systems (ETnGL) contains the class of isometric array languages under some stipulations which are used to regard an array as a graph. 相似文献
9.
A new language construct, called molecule, is described for the efficient implementation of algorithms on parallel computers. A molecule can be considered a procedure associated with a molecule type. Each molecule type characterizes a particular computation mode (sequential, pipelining, array processing, dataflow, multiprocessing, etc.). Basic concepts of molecule are introduced with a procedural language, called PAL. A concrete example is presented to illustrate layered software development using PAL on a multicomputer (the iPSC). It is concluded that high-level languages, augmented with the molecule construct, offer application flexibility, user friendliness, and efficiency in implementing parallel programs 相似文献
10.
针对大型拼接显示系统对PDF文件高分辨显示的需求,文中研究了集群并行高分辨信息显示平台的显示技术,分析了PDF在大屏显示系统中的重要性以及PDF文件格式和层次关系,研究并探讨了poppler库和mupdf库的优缺点,以及对PDF文件格式的解析与显示技术,并基于poppler库和mupdf库分别实现了PDF文件的解析和集群并行显示。通过对比实验,采用mupdf库能够更清晰、高效地实现PDF集群并行显示,验证了文中提出的PDF集群并行解析显示技术可极大地提高大型拼接显示系统对PDF文件的高分辨显示处理能力。 相似文献
11.
Parallel parsing is currently receiving attention but there is little discussion about the adaptation of sequential error handling techniques to these parallel algorithms. We describe a noncorrecting error handler implemented with a parallel LR substring parser. The parser used is a parallel version of Cormack's LR substring parser. The applicability of noncorrecting error handling for parallel parsing is discussed. The error information provided for a standard set of 118 erroneous Pascal programs is analysed. The programs are run on the sequential LR substring parser. 相似文献
12.
R.H. Perrott 《Computer Physics Communications》1982,26(3-4):267-275
This paper first considers the major developments which have occurred in the design of high level languages for sequential machines. These developments illustrate how languages which were independent of the hardware eventually evolved. Two major types of language for vector and parallel processors have evolved, namely, detection of parallelism languages and expression of machine parallelism languages. The disadvantages and advantages of each type of languages are examined. A third type of language is also considered which reflects neither the compiler's detection mechanism nor the underlying hardware. The syntax of this language enables the parallel nature of a problem to be expressed directly. The language is thus appropriate for both vector and array processors. 相似文献
13.
Junjie Gu Zhiyuan Li 《IEEE transactions on pattern analysis and machine intelligence》2000,26(3):244-261
Since sequential languages such as Fortran and C are more machine-independent than current parallel languages, it is highly desirable to develop powerful parallelization tools which can generate parallel codes, automatically or semi-automatically, targeting different parallel architectures. Array data-flow analysis is known to be crucial to the success of automatic parallelization. Such an analysis should be performed interprocedurally and symbolically and it often needs to handle the predicates represented by IF conditions. Unfortunately, such a powerful program analysis can be extremely time-consuming if it is not carefully designed. How to enhance the efficiency of this analysis to a practical level remains an issue largely untouched to date. This paper presents techniques for efficient interprocedural array data-flow analysis and documents experimental results of its implementation in a research parallelizing compiler. Our techniques are based on guarded array regions and the resulting tool runs faster, by one or two orders of magnitude, than other similarly powerful tools 相似文献
14.
Baumstark L.B. Jr. Wills L.M. 《IEEE transactions on pattern analysis and machine intelligence》2005,31(2):116-136
New compact, low-power implementation technologies for processors and imaging arrays can enable a new generation of portable video products. However, software compatibility with large bodies of existing applications written in C prevents more efficient, higher performance data parallel architectures from being used in these embedded products. If this software could be automatically retargeted explicitly for data parallel execution, product designers could incorporate these architectures into embedded products. The key challenge is exposing the parallelism that is inherent in these applications but that is obscured by artifacts imposed by sequential programming languages. This paper presents a recognition-based approach for automatically extracting a data parallel program model from sequential image processing code and retargeting it to data parallel execution mechanisms. The explicitly parallel model presented, called multidimensional data flow (MDDF), captures a model of how operations on data regions (e.g., rows, columns, and tiled blocks) are composed and interact. To extract an MDDF model, a partial recognition technique is used that focuses on identifying array access patterns in loops, transforming only those program elements that hinder parallelization, while leaving the core algorithmic computations intact. The paper presents results of retargeting a set of production programs to a representative data parallel processor array to demonstrate the capacity to extract parallelism using this technique. The retargeted applications yield a potential execution throughput limited only by the number of processing elements, exceeding thousands of instructions per cycle in massively parallel implementations. 相似文献
15.
Yuji Matsumoto 《New Generation Computing》1987,5(1):63-78
The paper presents a parallel parsing system for Definite Clause Grammars suitable for committed-choice parallel logic programming languages. Grammatical elements such as words and nonterminal symbols are defined as parallel processes. Parsing is done by the processcommunication. The advantage of the system is that all the grammar rules are compiled into the parallel logic programming language and the program has neither any side-effect nor duplicated computation. 相似文献
16.
Ujaldon M. Zapata E.L. Chapman B.M. Zima H.P. 《Parallel and Distributed Systems, IEEE Transactions on》1997,8(10):1068-1083
Vienna Fortran, High Performance Fortran (HPF), and other data parallel languages have been introduced to allow the programming of massively parallel distributed-memory machines (DMMP) at a relatively high level of abstraction, based on the SPMD paradigm. Their main features include directives to express the distribution of data and computations across the processors of a machine. In this paper, we use Vienna-Fortran as a general framework for dealing with sparse data structures. We describe new methods for the representation and distribution of such data on DMMPs, and propose simple language features that permit the user to characterize a matrix as “sparse” and specify the associated representation. Together with the data distribution for the matrix, this enables the complier and runtime system to translate sequential sparse code into explicitly parallel message-passing code. We develop new compilation and runtime techniques, which focus on achieving storage economy and reducing communication overhead in the target program. The overall result is a powerful mechanism for dealing efficiently with sparse matrices in data parallel languages and their compilers for DMMPs 相似文献
17.
Charles R. Dyer 《Information Sciences》1981,23(1):25-30
The class of languages accepted by one-way parallel/sequential acceptors (OPSA) is investigated for the two cases in which each OPSA cell is given memory size that is finite or proportional to the logarithm of the input size. It is shown that the class of languages accepted by the first type of OPSA is incomparable with the 2-D finite-state languages, whereas the class of languages accepted by the second type contains the 2-D finite-state languages. 相似文献
18.
19.
Roland Hausser 《Machine Translation》1988,3(1):23-67
The surface structures of natural language are linear. When we utter or understand a sentence, we process it word by word, starting at the beginning. But the associated semantic structures are hierarchical, expressed in terms of trees or set-theoretic relations. The correlation between linear syntax and hierarchical semantics is investigated in Left-Associative Grammar and the associated NEWCAT parsing algorithm. This paper gives a general outline of the linguistic theory. The formal algebraic and automata theoretic definitions will be presented in a second paper (Hausser, forthcoming), to appear in next issue of CaT. 相似文献
20.
Manfred Ruschitzka 《Future Generation Computer Systems》1990,5(4):373-380
Heterogeneous computer systems that are interconnected in today's computer networks lack efficient, general-purpose translation facilities for remote data. The provision of such facilities is potentially quite costly since the format of remote data is a function of the attributes of the remote architectures, operating systems, and software applications that maintain the data. This paper introduces a novel translation technique that parameterizes the translation process according to these attributes. Its formal specification is based on environment grammars, parameterized two-level grammars that lend themselves to the specification of classes of data languages with similar structures. We present a formal definition of environment grammars, discuss properties that permit their efficient parsing, and describe a data parsing method based on these properties. Examples illustrate the use of environment grammars for two different types of data languages. The viability of this parameterized technique has been demonstrated by an operational translation subsystem for data of heterogeneous relational database management systems. 相似文献