A division method of parallel gpdt algorithm on multi-core soc

A parallel computing and multi-core technology, applied in computing, computer components, CAD circuit design, etc., can solve problems such as large amount of calculation

Active Publication Date: 2020-07-03
FUDAN UNIV
View PDF6 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0043] The advantage of the GPDT algorithm is that the number of working set elements solved by each iteration can reach 10. 3 The order of magnitude enables the algorithm to converge quickly, but due to the large number of matrix operations in a single iteration, the amount of calculation is very large

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • A division method of parallel gpdt algorithm on multi-core soc
  • A division method of parallel gpdt algorithm on multi-core soc
  • A division method of parallel gpdt algorithm on multi-core soc

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0067] Below in conjunction with accompanying drawing, the present invention will be further described.

[0068] Such as figure 1 As shown, the present invention calculates the initial gradient in the algorithm middle The inner loop calculates the matrix z (k’) , the outer loop calculates the gradient increment The process is parallelized and distributed to multiple processors, which will greatly reduce the time of matrix operations in each iteration process. In addition, other parts of the algorithm are still serialized operations, including gradient projection and working set. update etc. According to Amdahl's law, the speedup ratio of the parallelized algorithm is not only related to the speedup ratio of the parallelizable part, but also related to the proportion of the parallelizable part. Therefore, as the training data increases, the proportion of computing time of the parallelizable part increases. , the overall speedup of the algorithm will gradually approach t...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

PUM

No PUM Login to view more

Abstract

The invention belongs to the technical field of integrated circuit design, and specifically relates to a method for dividing a parallel GPDT algorithm on a multi-core SoC. The parallel GPDT algorithm includes two iterations, the inner iteration is responsible for solving the working set, and the outer iteration is responsible for updating the working set. In terms of the critical path of calculation speed, the critical path of the outer loop is the update of the gradient, and the critical path of the inner loop is the calculation of the vector after each projection. These two parts of matrix operations need to be processed in parallel on multi-core; while the rest The calculations can only be implemented serially on the main core, including the gradient projection operation implemented by the Dai-Fletcher algorithm, and the update of the working set by introducing the quick sort algorithm. The vector obtained after the calculation is the support vector of the training data of the GPDT algorithm.

Description

technical field [0001] The invention belongs to the technical field of integrated circuit design, and specifically relates to a method for dividing a parallel GPDT algorithm on a multi-core SoC. Background technique [0002] The GPDT algorithm is a decomposition method for the original QP problem proposed by Zanni et al. The number of working set variables for each iteration is 10 2 to 10 3 Between the order of magnitude, the algorithm can reach convergence after a few iterations. Although the calculation amount of each iteration is relatively large, complex calculations can be distributed to multiple processors through parallelization, so that Get faster training speed. [0003] The original formulation of the SVM problem is: [0004] [0005] [0006] G is an l×l matrix, called the kernel matrix, where, is the kernel function. [0007] The decomposition of the problem is to divide the vector to be solved It is divided into two parts, one part is the working...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

Application Information

Patent Timeline
no application Login to view more
Patent Type & Authority Patents(China)
IPC IPC(8): G06F30/39G06K9/62
CPCG06F30/39G06F18/2411
Inventor 韩军轩四中袁腾跃曾晓洋
Owner FUDAN UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Try Eureka
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap