Packrat parsing is a powerful parsing algorithm presented by Ford in 2002. Packrat parsers can handle complicated grammars and recursive structures in lexical elements more easily than the traditional LL(k) or LR(1) parsing algorithms. However, packrat parsers require O(n) space for memoization, where n is the length of the input. This space inefficiency makes packrat parsers impractical in some applications. In our earlier work, we had proposed a packrat parser generator that accepts grammars extended with cut operators, which enable the generated parsers to reduce the amount of storage required.

String matching circuits have been studied extensively for intrusion detection systems so far. An NFA-based string matching circuit, one of the works, has expandability of processing data width. However the resource requirement increases markedly, it was difficult to implement an NFA-based string matching circuit with whole the Snort 2.3.3 rule (35461 characters) that processes at 10 Gbps on a single FPGA. In this paper, the authors propose a highly efficient string matching circuit for FPGA. In our circuit, redundant AND-gates and states in the NFA are eliminated to reduce the resource requirement. Consequently, our circuit is reduced in the resources requirement by over 50% as compared with a previous NFA-based circuit, and the synthesis result shows that a string matching circuit that includes the whole Snort 2.3.3 rule can be implemented onto a single xc2vp-100-6 FPGA with throughput over 10 Gbps

This paper proposes a method of generating a lightweight scalable NFA-based string matching circuit with elimination of redundant resources. String matching circuits have been studied extensively for intrusion detection systems. An NFA-based string matching circuit, one of the works, has expandability of the processing data width. Due to the huge hardware requirement, it was difficult to implement an NFA-based string matching circuit with the whole Snort 2.3.3 rule (35461 characters) that processes at 10 Gbps on a single FPGA. To reduce the circuit area, we eliminate redundant states of the NFA with the Aho-Corasick approach and redundant AND-gates in the NFA. Consequently, our method reduces the resource requirements by over 50% as compared with previous NFA-based circuits, and the synthesis result shows that a matching circuit that includes the whole Snort 2.3.3 rule can be implemented onto a single Xilinx Virtex-II pro xc2vp-100 with throughput over 10 Gbps

This report explicates the communication overlapping capabilities of three distributed-memory machines, SGI/Cray T3E, IBM SP-2 with wide nodes, and the ETL EM-X. Bitonic sorting and Fast Fourier Transform are selected for experiments. Various message sizes are used to determine when, where, how much and why the overlapping takes place. Experimental results with up to 64 processors indicated that the communication performance of EM-X is insensitive to various message sizes while SP-2 is the most sensitive. T3E stayed in between. The EM-X gave the highest communication overlapping capability while T3E did the lowest. The experimental results are compared with the analytical results based on LogP and LogGP communication models.

MPl point-to-point communication is a basic operation, however it requires runtime-matching of send and receive that causes to reduce performance.This paper proposes a new approach to send messages by remote memory write without inquiring of the receiver under a communication pattern such that nonblocking receive is issued in advance.Basically, this approach makes it possible to gain low latency and high bandwidth as the hardware specification.MPI-EMX, our implementation of the MPI on the EM-X multiprocessor, achieves a zero-byte latency of 13.4 psec.and a maximum bandwidth of 31.4MB/s, which can compete with commercial MPPs.This approach to reduce communication latency is widely applicable to other systems and is quite a promising technique for achieving low latency and high bandwidth.

No abstract available.

Article Fine-grain multithreading with the EM-X multiprocessor Share on Authors: Andrew Sohn Computer and Information Science Dept., New Jersey Institute of Technology, Newark, NJ Computer and Information Science Dept., New Jersey Institute of Technology, Newark, NJView Profile , Yuetsu Kodama Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, Japan Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, JapanView Profile , Jui Ku Computer and Information Science Dept., New Jersey Institute of Technology, Newark, NJ Computer and Information Science Dept., New Jersey Institute of Technology, Newark, NJView Profile , Mitsuhisa Sato Real World Computing Tsukuba Research Center, Tsukuba, Ibaraki, 305, Japan Real World Computing Tsukuba Research Center, Tsukuba, Ibaraki, 305, JapanView Profile , Hirofumi Sakane Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, Japan Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, JapanView Profile , Hayato Yamana Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, Japan Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, JapanView Profile , Shuichi Sakai Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, Japan Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, JapanView Profile , Yoshinori Yamaguchi Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, Japan Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, JapanView Profile Authors Info & Claims SPAA '97: Proceedings of the ninth annual ACM symposium on Parallel algorithms and architecturesJune 1997 Pages 189–198https://doi.org/10.1145/258492.258511Online:01 June 1997Publication History 7citation121DownloadsMetricsTotal Citations7Total Downloads121Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The purpose of this paper is to propose a new fast EM-4 multiprocessor to decrease the control overhead of macrotasks.Preliminary evaluations show that the control overhead of the proposed scheme is smaller than that of the other control schemes.Moreover, it is confirmed that the distributed control can be implemented by using software when the average macrotssk execution time is larger than 14.4ps on the EM-4 multiprocessor.

Latency tolerance is essential in achieving high performance on parallel computers for remote function calls and fine-grained remote memory accesses. EM-X supports interprocessor communication on an execution pipeline with small and simple packets. It can create a packet in one cycle, and receive a packet from the network in the on-chip buffer without interruption. EM-X invokes threads on packet arrival, minimizing the overhead of thread switching. It can tolerate communication latency by using efficient multi-threading and optimizing packet flow of fine grain communication. EM-X also supports the synchronization of two operands, direct remote memory read/write operations and flexible packet scheduling with priority. This paper describes distinctive features of the EM-X architecture and reports the performance of small synthetic programs and larger more realistic programs.

The design and performance of a priority forwarding router chip are presented. The chip has four input and four output ports, employs clock-synchronized packet switching, and facilitates 32-bit priority arbitration by means of a priority forwarding scheme that prevents priority inversion and enables accurate priority control within a network. Packets are of a fixed size, each having three 38-bit segments. Each input port has an 8-packet priority queue that enables virtual cut-through switching and pipelined-simultaneous output to at most three different output ports. The chip has two 25-ns pipeline stages and its data transmission rate is 190 MByte/s per port. Clock level simulation shows that the chip can attain high throughput, 9 GByte/s and 34 GByte/s at 64-node and 256-node omega networks with random communication, and excellent real-time performance. Very small laxities are required for in-time delivery of all input packets where the packets exhibit a degree of deadline distribution.>

Numeric scientific problems have been the main focus of supercomputing as their numerous implementations on various multiprocessors indicate. Nonnumeric problems on the other hand have received very little attention for parallel implementation due to their irregular behaviors and a large amount of resource usage. This report presents our experiences implementing difficult nonnumeric problems on the EM-4 multiprocessor, believing that supercomputers should also be able to effectively execute nonnumeric problems if they are to be considered 'supercomputers'. We selected two typical search problems, the Eight-Puzzle and the Tower-of-Hanoi. Two parallel search techniques we used to implement the search problems, unidirectional and bidirectional heuristic search. A total of eight different programs have been implemented on the EM-4 multiprocessor with realistic problem sizes. Execution results demonstrate that the parallel bidirectional heuristic search can solve the tree depth 20 to 40 of the Eight-Puzzle in an optimal or near optimal number of iterations in less than two seconds, and is highly scalable as it gives over 40-fold speedup for both problems on 80 processors.>

EMC-Y is a new processing element for highly parallel computers designed to achieve high performance parallel computation by fusing a dataflow mechanism and a von Neumann execution pipeline. We have already developed EMC-R, which is the processing element used in the EM-4 prototype. EMC-Y improves on EMC-R's packet communication performance, allowing it to tolerate a more network traffic. This paper presents the architecture of EMC-Y, concentrating on the principles of packet communication. EMC-Y uses an output packet buffer and optimal packet routing to improve the performance of packet sending and transferring. EMC-Y changes the memory access priority for input packet buffer operation to improve the performance of receiving packets. Since the EMC-Y processor not only improves the performance of packet input and output but also balances them, it can tolerate a large amount of traffic and can improve the execution performance. We evaluate the improvements of EMC-Y architecture using a clock level simulator. The results show that EMC-Y improves performance by 50% to 70% in several programs over EMC-R at the same clock speed.

In this paper, we present a thread-based programming model for the EM-4 hybrid dataflow machine, where parallelism and synchronization among threads of sequential execution are described explicitly by the programmer. Although EM-4 was originally designed as a dataflow machine, we demonstrate that it provides effective architectural support for a variety of programming styles, including message passing and distributed data sharing in imperative languages. Our approach allows the programmer to control the parallelism and maintain data locality explicitly to achieve high performance. EM-4 can be thought of as a multi-threaded architecture that can exploit both von Neumann and dataflow compiling technology. Thread-based programming provides the first step to explore better programming/compiling technology for a hybrid dataflow machine as well as EM-4.

The EM-4 is a highly parallel daiaflow machine that will eventually have more than 1,000 processing elements (PEs). This paper presents load balancing methods by function distribution in the EM-4 and their evaluations on the EM-4 prototype, which con-sists of 80 PEs. The EM-4 can distribute function in-stances statically by using several different allocation functions, including a method exploiting the locality of the network. Furthermore, the EM-4 can dynami-cally distribute function instances using MLPE packets which circulate through the PEs and detect the local-minimum load PE. These function distn’bution meth-ods are evaluated by executing a divide-and-conquer program and a game tree searching program, and ex-amining its dynamic characteristics on every PE. 1

This paper describes the research activity on dataflow computing in Japan focusing on dataflow computer development at the Electrotechnical Laboratory (ETL). First, the history of dataflow computer development in Japan is outlined. Some distinguished milestones in the history are mentioned in detail. Second, two types of dataflow computing systems developed at ETL, SIGMA-1 and EM-4, are described with their research goals. The fundamental characteristics of the both systems are given and some comparisons are made. Finally, future problems toward new generation computer systems to meet the challenge of Tera FLOPS machines are discussed.

A highly parallel (more than a thousand) dataflow machine EM-4 is now under development. The EM-4 design principle is to construct a high performance computer using a compact architecture by overcoming several defects of dataflow machines. Constructing the EM-4, it is essential to fabricate a processing element (PE) on a single chip for reducing operation speed, system size, design complexity and cost. In the EM-4, the PE , called EMC-R, has been specially designed using a 50,000-gate gate array chip. This paper focuses on an architecture of the EMC-R. The distinctive features of it are: a strongly connected arc dataflow model; a direct matching scheme; a RISC-based design; a deadlock-free on-chip packet switch; and an integration of a packet-based circular pipeline and a register-based advanced control pipeline. These features are intensively examined, and the instruction set architecture and the configuration architecture which exploit them are described.

The authors compare dataflow computing models, languages, and dataflow computing machines for numerical and nonnumerical computations. The high-level-language-graph transformations that must be performed to achieve high performance for numerical and nonnumerical programs executed in a dataflow computing environment are described for Lisp, using the DCBL transformations. Some general problems of dataflow computing machines are discussed. Performance evaluation measurements obtained by executing benchmark programs in the ETL nonnumerical dataflow computing environment, the EM-3, are presented.>

In this paper, a Lisp-based data-driven machine with a novel parallel control mechanism and its performance evaluation are presented. The proposed control mechanism is the natural extension of a data-driven scheme to function evaluation and is achieved by packet communication architecture. First, the organization of the data-driven machine is described and, then the results of the simulation studies are shown which confirm the effectiveness of the control mechanism. The performance characteristics of the data-driven machine obtained by the software simulator are also given.