IP Library Granted Patent US 9,858,056
Granted Patent B1
US 9,858,056 · App. 15/212,547 · Granted Jan 2, 2018

Accelerated content analytics based on a hierarchical data-flow-graph representation

Inventors: Kubilay Atasu (Horgen, CH); Akihiro Nakayama (Kanagawa, JP); Raphael Polig (Dietikon, CH); Tong Xu (Ontario, CA)
Assignee: International Business Machines Corporation
G06F8/4441G06F8/433
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 9,858,056
App. No.
15/212,547
Granted
Jan 2, 2018
Kind
B1
Abstract

A system and method to hardware-accelerate finite state transducer libraries and their compilation toolchains. In an embodiment, a computer-implemented method for partitioning an UIMA-PEAR file into software-based and hardware-accelerated components may comprise creating a data-flow graph representation of the UIMA-PEAR-file, flattening hierarchies of the data-flow graph representation, and selecting the components to be hardware accelerated from the flattened hierarchies of the data-flow graph representation based on data dependencies of data types produced and consumed by each component of the flattened data-flow graph.

Claims (56)

1. A computer-implemented method for partitioning an Unstructured Information Management Architecture (UIMA)-Processing Engine ARchive (PEAR) file into software-based and hardware-accelerated components comprising:

creating a data-flow graph representation of the UIMA-PEAR file;

evaluating the software and hardware complexity of each component of the data-flow graph representation;

flattening hierarchies of the data-flow graph representation; and

selecting the components to be hardware accelerated from the flattened hierarchies of the data-flow graph representation based on data dependencies of data types produced and consumed by each component of the flattened data-flow graph, wherein selecting the components to be hardware accelerated comprises:

removing off-loadable software components from analysis engines, wherein the highest level of hierarchy of the data-flow graph representation is composed of the analysis engines and wherein each analysis engine is a composition of a set of library-based or user-defined software components;

removing analysis engines that have no more off-loadable software components:

merging remaining analysis engines to form new hardware-based components while preserving the data dependencies of the data types, wherein at least some of the merged analysis engines are from different levels of hierarchy of the data-flow graph representation of the UIMA-PEAR file; and

adding the new hardware-based components to be implemented in hardware.

2. The method of claim 1 , wherein the data-flow graph representation comprises:

a plurality of nodes, each node representing a component that either produces data or consumes data; and

a plurality of edges, each edge representing a data type and connecting a component that produces the data type with a component that consumes the data type.

3. The method of claim 2 , wherein evaluating software and hardware complexity of each component comprises:

determining a software execution time spent on each component; and

determining resources needed to implement each component.

4. The method of claim 3 , further comprising:

mapping software-based components into resources of a hardware accelerator.

5. The method of claim 3 , further comprising:

mapping multiple software-based components into resources of a hardware accelerator to form a data-flow pipeline.

6. A computer program product for partitioning an Unstructured information Management Architecture (UIMA)-Processing Engine ARchive (PEAR) file into software-based and hardware-accelerated components, the computer program product comprising a non-transitory computer readable storage having program instructions embodied therewith, the program instructions executable by a computer, to cause the computer to perform a method comprising:

creating a data-flow graph representation of the UIMA-PEAR-file;

evaluating the software and hardware complexity of each component of the data-flow graph representation;

flattening hierarchies of the data-flow graph representation; and

selecting the components to be hardware accelerated from the flattened hierarchies of the data-flow graph representation based on data dependencies of data types produced and consumed by each component of the flattened data-flow graph, wherein selecting the components to be hardware accelerated comprises:

removing off-loadable software components from analysis engines, wherein the highest level of hierarchy of the data-flow graph representation is composed of the analysis engines and wherein each analysis engine is a composition of a set of library-based or user-defined software components;

removing analysis engines that have no more off-loadable software components;

merging remaining analysis engines to form new hardware-based components while preserving the data dependencies of the data types, wherein at least some of the merged analysis engines are from different levels of hierarchy of the data-flow graph representation of the UIMA-PEAR file; and

adding the new hardware-based components to be implemented in hardware.

7. The computer program product of claim 6 , wherein the data-flow graph representation comprises:

a plurality of nodes, each node representing a component that either produces data or consumes data; and

a plurality of edges, each edge representing a data type and connecting a component that produces the data type with a component that consumes the data type.

8. The computer program product of claim 7 , wherein evaluating software and hardware complexity of each component comprises:

determining a software execution time spent on each component; and

determining resources needed to implement each component.

9. The computer program product of claim 8 , further comprising program instructions for:

mapping software-based components into resources of a hardware accelerator.

10. The computer program product of claim 8 , further comprising program instructions for:

mapping multiple software-based components into resources of a hardware accelerator to form a data-flow pipeline.

11. A system for partitioning an Unstructured Information Management Architecture (UIMA)-Processing Engine ARchive (PEAR) file into software-based and hardware-accelerated components, the system comprising a processor, memory accessible by the processor, and computer program instructions stored in the memory and executable by the processor to perform:

creating a data-flow graph representation of the UIMA-PEAR-file;

flattening hierarchies of the data-flow graph representation; and

selecting the components to be hardware accelerated from the flattened hierarchies of the data-flow graph representation based on data dependencies of data types produced and consumed by each component of the flattened data-flow graph, wherein selecting the components to be hardware accelerated comprises:

removing off-loadable software components from analysis engines, wherein the highest level of hierarchy of the data-flow graph representation is composed of the analysis engines and wherein each analysis engine is a composition of a set of library-based or user-defined software components;

removing analysis engines that have no more off-loadable software components;

merging remaining analysis engines to form new hardware-based components while preserving the data dependencies of the data types, wherein at least some of the merged analysis engines are from different levels of hierarchy of the data-flow graph representation of the UIMA-PEAR file; and

adding the new hardware-based components to be implemented in hardware.

12. The system of claim 11 , wherein the data-flow graph representation comprises:

a plurality of nodes, each node representing a component that either produces data or consumes data; and

a plurality of edges, each edge representing a data type and connecting a component that produces the data type with a component that consumes the data type.

13. The system of claim 12 , wherein evaluating software and hardware complexity of each component comprises:

determining a software execution time spent on each component; and

determining resources needed to implement each component.

14. The system of claim 13 , further comprising computer program instructions for:

mapping software-based components into resources of a hardware accelerator.

15. The system of claim 13 , further comprising computer program instructions for:

mapping multiple software-based components Into resources of a hardware accelerator to form a data-flow pipeline.

Assignments (2)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Oct 15, 2021
From: INTERNATIONAL BUSINESS MACHINES CORPORATION
To: DOORDASH, INC.
Reel/Frame 057826/0939 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jul 18, 2016
From: ATASU, KUBILAY; NAKAYAMA, AKIHIRO; POLIG, RAPHAEL; XU, TONG
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 039177/0396 →