公开(公告)号：US10019190B2

公开(公告)日：2018-07-10

申请号：US14831775

申请日：2015-08-20

Applicant: NEC Laboratories America, Inc.

Inventor： Kunal Rao ,  Giuseppe Coviello ,  Srimat Chakradhar ,  Souvik Bhattacherjee ,  Srihari Cadambi

IPC: G06F17/30 ,  G06F3/06 ,  G06T11/20

CPC classification number: G06F16/9535 ,  G06F16/2358 ,  G06F16/2365 ,  G06F16/2372 ,  G06F16/245 ,  G06F16/9024 ,  G06F16/955 ,  G06T11/206

Abstract: A method for detecting abnormal changes in real-time in dynamic graphs. The method includes extracting, by a graph sampler, an active sampled graph from an underlying base graph. The method further includes merging, by a graph merger, the active sampled graph with graph updates within a predetermined recent time period to generate a merged graph. The method also includes computing, by a graph diameter computer, a diameter of the merged graph. The method additionally includes determining, by a graph diameter change determination device, whether a graph diameter change exists. The method further includes generating, by an alarm generator, a user-perceptible alarm responsive to the graph diameter change.

公开(公告)号：US09965209B2

公开(公告)日：2018-05-08

申请号：US14831809

申请日：2015-08-20

Applicant: NEC Laboratories America, Inc.

Inventor： Kunal Rao ,  Giuseppe Coviello ,  Srimat Chakradhar ,  Souvik Bhattacherjee ,  Srihari Cadambi

IPC: G06F3/06 ,  G06F17/30 ,  G06T11/20

CPC classification number: G06F3/0638 ,  G06F3/0604 ,  G06F3/0619 ,  G06F3/067 ,  G06F17/30368 ,  G06F17/30371 ,  G06F17/30374 ,  G06F17/30424 ,  G06F17/30867 ,  G06F17/30876 ,  G06F17/30958 ,  G06T11/206

Abstract: A method in a graph storage and processing system is provided. The method includes storing, in a scalable, distributed, fault-tolerant, in-memory graph storage device, base graph data representative of graphs, and storing, in a real-time, in memory graph storage device, update graph data representative of graph updates for the graphs with respect to a time threshold. The method further includes sampling the base graph data to generate sampled portions of the graphs and storing the sampled portions, by an in-memory graph sampler. The method additionally includes providing, by a query manager, a query interface between applications and the system. The method also includes forming, by the query manager, graph data representative of a complete graph from at least the base graph data and the update graph data, if any. The method includes processing, by a graph computer, the sampled portions using batch-type computations to generate approximate results for graph-based queries.

公开(公告)号：US09720597B2

公开(公告)日：2017-08-01

申请号：US14603813

申请日：2015-01-23

Applicant: NEC Laboratories America, Inc.

Inventor： Cheng-Hong Li ,  Giuseppe Coviello ,  Kunal Rao ,  Murugan Sankaradas ,  Srihari Cadambi ,  Srimat Chakradhar ,  Rajat Phull

IPC: G06F12/00 ,  G06F3/06 ,  G06F9/50

CPC classification number: G06F3/061 ,  G06F3/0656 ,  G06F3/0673 ,  G06F9/50 ,  G06F12/023

Abstract: Systems and methods for swapping out and in pinned memory regions between main memory and a separate storage location in a system, including establishing an offload buffer in an interposing library; swapping out pinned memory regions by transferring offload buffer data from a coprocessor memory to a host processor memory, unregistering and unmapping a memory region employed by the offload buffer from the interposing library, wherein the interposing library is pre-loaded on the coprocessor, and collects and stores information employed during the swapping out. The pinned memory regions are swapped in by mapping and re-registering the files to the memory region employed by the offload buffer, and transferring data of the offload buffer data from the host memory back to the re-registered memory region.

公开(公告)号：US20140208072A1

公开(公告)日：2014-07-24

申请号：US13858034

申请日：2013-04-06

Applicant: NEC LABORATORIES AMERICA, INC.

Inventor： Srihari Cadambi ,  Kunal Rao ,  Srimat T. Chakradhar ,  Rajat Phull ,  Giuseppe Coviello ,  Murugan Sankaradass ,  Cheng-Hong Li

IPC: G06F9/48

CPC classification number: G06F9/5044 ,  G06F9/5033 ,  G06F2209/509

Abstract: A method is disclosed to manage a multi-processor system with one or more multiple-core coprocessors by intercepting coprocessor offload infrastructure application program interface (API) calls; scheduling user processes to run on one of the coprocessors; scheduling offloads within user processes to run on one of the coprocessors; and affinitizing offloads to predetermined cores within one of the coprocessors by selecting and allocating cores to an offload, and obtaining a thread-to-core mapping from a user.

Abstract translation: 公开了一种通过拦截协处理器卸载基础设施应用程序接口（API）调用来管理具有一个或多个多核协处理器的多处理器系统的方法; 调度用户进程以在一个协处理器上运行; 在用户进程内调度卸载以在一个协处理器上运行; 并且通过选择和分配核到卸载来将卸载到一个协处理器内的预定内核，并从用户获得线程到核心的映射。

公开(公告)号：US10162550B2

公开(公告)日：2018-12-25

申请号：US14831792

申请日：2015-08-20

Applicant: NEC Laboratories America, Inc.

Inventor： Kunal Rao ,  Giuseppe Coviello ,  Srimat Chakradhar ,  Souvik Bhattacherjee ,  Srihari Cadambi

IPC: G06F3/06 ,  G06F17/30 ,  G06T11/20

Abstract: A graph storage and processing system is provided. The system includes a scalable, distributed, fault-tolerant, in-memory graph storage device for storing base graph data representative of graphs. The system further includes a real-time, in memory graph storage device for storing update graph data representative of graph updates for the graphs with respect to a time threshold. The system also includes an in-memory graph sampler for sampling the base graph data to generate sampled portions of the graphs and for storing the sampled portions of the graph. The system additionally includes a query manager for providing a query interface between applications and the system and for forming graph data representative of a complete graph from at least the base graph data and the update graph data, if any. The system also includes a graph computer for processing the sampled portions using batch-type computations to generate approximate results for graph-based queries.

公开(公告)号：US09152467B2

公开(公告)日：2015-10-06

申请号：US13858039

申请日：2013-04-06

Applicant: NEC Laboratories America, Inc.

Inventor： Srihari Cadambi ,  Kunal Rao ,  Srimat T. Chakradhar ,  Rajat Phull ,  Giuseppe Coviello ,  Murugan Sankaradass ,  Cheng-Hong Li

IPC: G06F9/46 ,  G06F9/50

CPC classification number: G06F9/5044 ,  G06F9/5033 ,  G06F2209/509

Abstract: A method is disclosed to manage a multi-processor system with one or more manycore devices, by managing real-time bag-of-tasks applications for a cluster, wherein each task runs on a single server node, and uses the offload programming model, and wherein each task has a deadline and three specific resource requirements: total processing time, a certain number of manycore devices and peak memory on each device; when a new task arrives, querying each node scheduler to determine which node can best accept the task and each node scheduler responds with an estimated completion time and a confidence level, wherein the node schedulers use an urgency-based heuristic to schedule each task and its offloads; responding to an accept/reject query phase, wherein the cluster scheduler send the task requirements to each node and queries if the node can accept the task with an estimated completion time and confidence level; and scheduling tasks and offloads using a aging and urgency-based heuristic, wherein the aging guarantees fairness, and the urgency prioritizes tasks and offloads so that maximal deadlines are met.

Abstract translation: 公开了一种通过管理用于集群的实时任务应用程序来管理具有一个或多个管理器设备的多处理器系统的方法，其中每个任务在单个服务器节点上运行，并且使用卸载编程模型， 并且其中每个任务具有最后期限和三个特定的资源要求：总处理时间，一定数量的管理设备和每个设备上的峰值存储器; 当新任务到达时，查询每个节点调度器以确定哪个节点可以最好地接受任务，并且每个节点调度器以估计的完成时间和置信水平进行响应，其中节点调度器使用基于紧急度的启发式来安排每个任务及其 卸货 响应于接受/拒绝查询阶段，其中所述群集调度器向每个节点发送所述任务需求，并且查询所述节点是否可以接收具有估计完成时间和置信水平的所述任务; 并使用基于老化和紧急性的启发式调度任务和卸载，其中老化保证公平性，并且紧急性优先考虑任务和卸载，以便满足最大期限。

公开(公告)号：US20140237477A1

公开(公告)日：2014-08-21

申请号：US14261090

申请日：2014-04-24

Applicant: NEC Laboratories America, Inc.

Inventor： Srihari Cadambi ,  Kunal Rao ,  Srimat Chakradhar ,  Rajat Phull ,  Giuseppe Coviello ,  Murugan Sankaradass ,  Cheng-Hong Li

IPC: G06F9/46

CPC classification number: G06F9/5044 ,  G06F9/4881

Abstract: Methods and systems for scheduling jobs to manycore nodes in a cluster include selecting a job to run according to the job's wait time and the job's expected execution time; sending job requirements to all nodes in a cluster, where each node includes a manycore processor; determining at each node whether said node has sufficient resources to ever satisfy the job requirements and, if no node has sufficient resources, deleting the job; creating a list of nodes that have sufficient free resources at a present time to satisfy the job requirements; and assigning the job to a node, based on a difference between an expected execution time and associated confidence value for each node and a hypothetical fastest execution time and associated hypothetical maximum confidence value.

Abstract translation: 将作业调度到群集节点的方法和系统包括根据作业的等待时间和作业的预期执行时间来选择要运行的作业; 向群集中的所有节点发送作业需求，其中每个节点包括一个处理器; 在每个节点处确定所述节点是否具有足够的资源以满足工作要求，如果没有节点具有足够的资源，则删除该作业; 创建一个目前有足够空闲资源的节点列表，以满足工作要求; 并且基于每个节点的预期执行时间和相关联的置信度值之间的差异以及假设的最快执行时间和相关联的假设最大置信度值将作业分配给节点。

公开(公告)号：US09367357B2

公开(公告)日：2016-06-14

申请号：US14261090

申请日：2014-04-24

Applicant: NEC Laboratories America, Inc.

Inventor： Srihari Cadambi ,  Kunal Rao ,  Srimat Chakradhar ,  Rajat Phull ,  Giuseppe Coviello ,  Murugan Sankaradass ,  Cheng-Hong Li

IPC: G06F9/46 ,  G06F9/50 ,  G06F9/48

CPC classification number: G06F9/5044 ,  G06F9/4881

Abstract: Methods and systems for scheduling jobs to manycore nodes in a cluster include selecting a job to run according to the job's wait time and the job's expected execution time; sending job requirements to all nodes in a cluster, where each node includes a manycore processor; determining at each node whether said node has sufficient resources to ever satisfy the job requirements and, if no node has sufficient resources, deleting the job; creating a list of nodes that have sufficient free resources at a present time to satisfy the job requirements; and assigning the job to a node, based on a difference between an expected execution time and associated confidence value for each node and a hypothetical fastest execution time and associated hypothetical maximum confidence value.

Abstract translation: 将作业调度到群集节点的方法和系统包括根据作业的等待时间和作业的预期执行时间来选择要运行的作业; 向群集中的所有节点发送作业需求，其中每个节点包括一个处理器; 在每个节点处确定所述节点是否具有足够的资源以满足工作要求，如果没有节点具有足够的资源，则删除该作业; 创建一个目前有足够空闲资源的节点列表，以满足工作要求; 并且基于每个节点的预期执行时间和相关联的置信度值之间的差异以及假设的最快执行时间和相关联的假设最大置信度值将作业分配给节点。

公开(公告)号：US20160110409A1

公开(公告)日：2016-04-21

申请号：US14831809

申请日：2015-08-20

Applicant: NEC Laboratories America, Inc.

Inventor： Kunal Rao ,  Giuseppe Coviello ,  Srimat Chakradhar ,  Souvik Bhattacherjee ,  Srihari Cadambi

IPC: G06F17/30 ,  G06T11/20

CPC classification number: G06F3/0638 ,  G06F3/0604 ,  G06F3/0619 ,  G06F3/067 ,  G06F17/30368 ,  G06F17/30371 ,  G06F17/30374 ,  G06F17/30424 ,  G06F17/30867 ,  G06F17/30876 ,  G06F17/30958 ,  G06T11/206

Abstract: A method in a graph storage and processing system is provided. The method includes storing, in a scalable, distributed, fault-tolerant, in-memory graph storage device, base graph data representative of graphs, and storing, in a real-time, in memory graph storage device, update graph data representative of graph updates for the graphs with respect to a time threshold. The method further includes sampling the base graph data to generate sampled portions of the graphs and storing the sampled portions, by an in-memory graph sampler. The method additionally includes providing, by a query manager, a query interface between applications and the system. The method also includes forming, by the query manager, graph data representative of a complete graph from at least the base graph data and the update graph data, if any. The method includes processing, by a graph computer, the sampled portions using batch-type computations to generate approximate results for graph-based queries.

Abstract translation: 提供了图形存储和处理系统中的一种方法。 该方法包括在可扩展的，分布式的，容错的存储器内存图形存储装置中存储表示图形的基本图形数据，并且实时地存储在存储器图形存储装置中，代表图形的更新图形数据 相对于时间阈值更新图表。 该方法还包括对基本图形数据进行采样以生成图形的采样部分并通过存储器内图形采样器存储采样部分。 该方法还包括由查询管理器提供应用和系统之间的查询接口。 该方法还包括由查询管理器从至少基本图形数据和更新图形数据（如果有的话）形成表示完整图形的图形数据。 该方法包括通过图形计算机处理使用分批式计算的采样部分，以生成基于图形的查询的近似结果。

公开(公告)号：US20150212733A1

公开(公告)日：2015-07-30

申请号：US14603813

申请日：2015-01-23

Applicant: NEC Laboratories America, Inc.

Inventor： Cheng-Hong LI ,  Giuseppe Coviello ,  Kunal Rao ,  Murugan Sankaradas ,  Srihari Cadambi ,  Srimat Chakradhar ,  Rajat Phull

IPC: G06F3/06

CPC classification number: G06F3/061 ,  G06F3/0656 ,  G06F3/0673 ,  G06F9/50 ,  G06F12/023

Abstract: Systems and methods for swapping out and in pinned memory regions between main memory and a separate storage location in a system, including establishing an offload buffer in an interposing library; swapping out pinned memory regions by transferring offload buffer data from a coprocessor memory to a host processor memory, unregistering and unmapping a memory region employed by the offload buffer from the interposing library, wherein the interposing library is pre-loaded on the coprocessor, and collects and stores information employed during the swapping out. The pinned memory regions are swapped in by mapping and re-registering the files to the memory region employed by the offload buffer, and transferring data of the offload buffer data from the host memory back to the re-registered memory region.

Abstract translation: 用于在主存储器和系统中的单独存储位置之间交换出和被固定的存储器区域的系统和方法，包括在插入库中建立卸载缓冲器; 通过将协处理器存储器中的卸载缓冲器数据传送到主机处理器存储器来交换出固定的存储器区域，从插入库取消注册和解映射卸载缓冲器所使用的存储器区域，其中插入库被预加载到协处理器上，并且收集 并存储在交换期间使用的信息。 通过将文件映射并重新注册到由卸载缓冲器采用的存储器区域并将卸载缓冲器数据的数据从主机存储器传送回重新注册的存储器区域来交换被固定的存储器区域。