公开(公告)号：US4860201A

公开(公告)日：1989-08-22

申请号：US902547

申请日：1986-09-02

申请人： Salvatore J. Stolfo ,  Daniel P. Miranker

发明人： Salvatore J. Stolfo ,  Daniel P. Miranker

IPC分类号： G06F15/16 ,  G06F9/44 ,  G06F11/00 ,  G06F11/10 ,  G06F11/14 ,  G06F11/16 ,  G06F11/22 ,  G06F15/173 ,  G06F15/80 ,  G06F17/30 ,  G06N5/00

CPC分类号： G06F17/30988 ,  G06F11/0724 ,  G06F15/17337 ,  G06F15/8023 ,  G06F9/4436 ,  G06N5/00 ,  G06F11/0757 ,  G06F11/10 ,  G06F11/14 ,  G06F11/22

摘要： A plurality of parallel processing elements are connected in a binary tree configuration, with each processing element except those in the highest and lowest levels being in communication with a single parent processing element as well as first and second (or left and right) child processing elements. Each processing element comprises a processor, a read/write or random access memory, and an input/output (I/O) device. The I/O device provides interfacing between each processing element and its parent and children processing elements so as to provide significant improvements in propagation speeds through the binary tree. The I/O device allows the presently preferred embodiment of the invention to be clocked at 12 megahertz, producing in the case of a tree of 1023 processors, each having an average instruction cycle time of 1.8 .mu.s, a system with a raw computational throughput of approximately 570 million instructions per second. The I/O device communicates data and queries from the root processing element to all other N processing elements in the array in one processor instruction cycle instead of in O(log.sub.2 N) processor instruction cycles as in prior art binary tree arrays. Primitive queries are executed in parallel by each processing element and the results made available for reporting back to the root processing element. In several important cases, these results can be combined and reported back to the root processing element in a single processor instruction cycle instead of in O(log.sub.2 N) processor instruction cycles as in prior art binary tree arrays. Thus, the elapsed time for a broadcast and report operation is in effect a constant time regardless of the number of processors in the array.

摘要翻译： 多个并行处理元件以二叉树配置连接，除了最高和最低级中的每个处理元件与单个父处理元件以及第一和第二（或左和右）子处理元件 。 每个处理元件包括处理器，读/写或随机存取存储器以及输入/输出（I / O）设备。 I / O设备提供每个处理元件与其父和子处理元件之间的接口，以便通过二叉树提供传播速度的显着改进。 I / O设备允许将本发明的当前优选实施例定时为12兆赫，在1023个处理器的树的情况下产生，每个处理器的平均指令周期时间为1.8μs，具有原始计算吞吐量的系统 每秒约5.7亿条指令。 I / O设备在一个处理器指令周期内将数据和来自根处理元件的数据和查询传送到阵列中的所有其他N个处理元件，而不是象现有技术的二叉树阵列那样处于O（log2N）处理器指令周期中。 原始查询由每个处理元素并行执行，结果可用于向根处理元素报告。 在几个重要的情况下，这些结果可以在单个处理器指令周期中组合并返回给根处理元素，而不是像现有技术的二叉树数组那样在O（log2N）处理器指令周期内。 因此，与阵列中的处理器数量无关，广播和报告操作的经过时间实际上是恒定的时间。

公开(公告)号：US06782505B1

公开(公告)日：2004-08-24

申请号：US09294701

申请日：1999-04-19

申请人： Daniel P. Miranker ,  L. Lance Obermeyer ,  Paul A. Navratil

发明人： Daniel P. Miranker ,  L. Lance Obermeyer ,  Paul A. Navratil

IPC分类号： G06F1500

CPC分类号： G06F17/2715 ,  G06F17/2247 ,  G06F17/271 ,  G06F17/272 ,  G06F17/277 ,  G06F17/30569 ,  G06K9/62 ,  G06K9/72 ,  Y10S707/99943

摘要： A system and method for generating structured data outputs from a semi-structured data source. The steps of this method include generating an example output from an example generator. The example output is generated in response to the acquisition of a sequence of annotated strings. The annotated strings are generated in response to the acquisition and modification of at least one data example and corresponding coarse structure from a predetermined input source. Also, a second sequence of annotated strings is generated from input from a semi-structured data source. Both the example output and second sequence of annotated strings are input to an acquisition engine that implements a grammar layer incorporating a top-down parsing method and a comparison layer. The structured data outputs are generated through the cooperation of the comparison layer and the grammar layer.

摘要翻译： 一种用于从半结构化数据源生成结构化数据输出的系统和方法。 该方法的步骤包括从示例生成器生成示例输出。 响应于获取注释字符串序列而生成示例输出。 响应于来自预定输入源的至少一个数据示例和对应的粗略结构的获取和修改而产生注释的字符串。 此外，从半结构化数据源的输入生成注释字符串的第二序列。 注释字符串的示例输出和第二序列都输入到实现包含自顶向下解析方法和比较层的语法层的采集引擎。 结构化数据输出是通过比较层和语法层的协作生成的。