公开(公告)号：US20230195793A1

公开(公告)日：2023-06-22

申请号：US17799278

申请日：2021-09-22

Applicant: SHANGHAITECH UNIVERSITY

Inventor： Guangyao YAN ,  Xinzhe LIU ,  Yajun HA ,  Hui WANG

IPC: G06F16/901

CPC classification number: G06F16/9024

Abstract: A ripple push method for a graph cut includes: obtaining an excess flow ef(v) of a current node v; traversing four edges connecting the current node v in top, bottom, left and right directions, and determining whether each of the four edges is a pushable edge; calculating, according to different weight functions, a maximum push value of each of the four edges by efw=ef(v)*W, where W denotes a weight function; and traversing the four edges, recording a pushable flow of each of the four edges, and pushing out a calculated flow. The ripple push method explores different push weight functions, and significantly improves the actual parallelism of the push-relabel algorithm.

公开(公告)号：US20210248764A1

公开(公告)日：2021-08-12

申请号：US17054169

申请日：2020-06-17

Applicant: SHANGHAITECH UNIVERSITY

Inventor： Xinzhe LIU ,  Fupeng CHEN ,  Yajun HA

IPC: G06T7/44 ,  G06F9/38 ,  G06F9/54 ,  G06F9/30 ,  G06F1/10

Abstract: An efficient parallel computing method for a box filter, includes: step 1, with respect to a given degree of parallelism N and a radius r of the filter kernel, establishing a first architecture provided without an extra register and a second architecture provided with the extra register; step 2, building a first adder tree for the first architecture and a second adder tree for the second architecture, respectively; step 3, searching the first adder tree and the second adder tree from top to bottom, calculating the pixel average corresponding to each filter kernel by using the first adder tree and the second adder tree, respectively, and counting resources required to be consumed by the first architecture and the second architecture, respectively; and, step 4, selecting one architecture consuming a relatively small resources from the first architecture and the second architecture for computing the box filter.

公开(公告)号：US20240273273A1

公开(公告)日：2024-08-15

申请号：US18401731

申请日：2024-01-02

Applicant: SHANGHAITECH UNIVERSITY

Inventor： Guangyao YAN ,  Xinzhe LIU ,  Yajun HA ,  Hui WANG

IPC: G06F30/347 ,  G06F30/392 ,  G06F111/10 ,  G06F115/10

CPC classification number: G06F30/347 ,  G06F30/392 ,  G06F2111/10 ,  G06F2115/10

Abstract: A disordered parallel maximum flow/minimum cut method implemented by an energy-efficient field-programmable gate array (FPGA) folds a single-layer large two-dimensional grid graph into a multi-layer small grid graph. The method enables a folding grid architecture to store and process a grid graph that is much larger than a processor array in size. The folding grid architecture endows a two-dimensional processor array with a degree of freedom in a vertical direction, such that the two-dimensional processor array can leverage a potential for parallel performance of the folding grid architecture based on the degree of freedom in the vertical direction. The folding grid architecture enables a small-sized processor array to have an ability to process a grid graph that is much larger than the small-sized processor array in size. In addition, based on axial symmetry of folding, the folding grid architecture can greatly reduce cross-boundary transmission of data in the processor array.

公开(公告)号：US20240220770A1

公开(公告)日：2024-07-04

申请号：US18387463

申请日：2023-11-07

Applicant: SHANGHAITECH UNIVERSITY

Inventor： Shen ZHANG ,  Xinzhe LIU ,  Yajun HA

IPC: G06N3/04 ,  G06N5/04 ,  G06N7/01

CPC classification number: G06N3/04 ,  G06N5/04 ,  G06N7/01

Abstract: A high-efficient quantization method for a deep probabilistic network achieves good result through hybrid quantization, structure reformulation, and type optimization. Firstly, for a directed acyclic graph (DAG) structure, all nodes in the DAG are clustered, and each node is quantized by a specific arithmetic type based on the clustering category, to obtain a preliminarily quantized deep probabilistic network. Secondly, the multi-in nodes in a preliminarily quantized deep probabilistic network are reformulated based on the input weights, structural reformulation converts a multi-in node into a binary tree network containing only two-input nodes, and parametrical reformulation is performed on the reformulated structure. Finally, arithmetic types of all nodes are optimized by using an arithmetic type search method based on power consumption analysis and network accuracy analysis. The method can significantly reduce computational complexity and energy consumption for computing while maintaining model accuracy of the deep probabilistic network.

公开(公告)号：US20240112443A1

公开(公告)日：2024-04-04

申请号：US17798898

申请日：2021-09-22

Applicant: SHANGHAITECH UNIVERSITY

Inventor： Xinzhe LIU ,  Guangyao YAN ,  Yajun HA

IPC: G06V10/762 ,  G06V10/764 ,  G06V10/96

CPC classification number: G06V10/7635 ,  G06V10/764 ,  G06V10/96

Abstract: A max-flow/min-cut solution algorithm for early terminating a push-relabel algorithm is provided. The max-flow/min-cut solution algorithm is used for an application that does not require an exact maximum flow, and includes: defining an early termination condition of the push-relabel algorithm by a separation condition and a stable condition; determining that the separation condition is satisfied if there is no source node s, s∈S, in the set T at any time in an operation process of the push-relabel algorithm; determining that the stable condition is satisfied if there is no active node in the set T; and terminating the push-relabel algorithm if both the separation condition and the stability condition are satisfied. The early termination technique is proposed to greatly reduce redundant computations and ensure that the algorithm terminates correctly in all cases.