Skip to content

Software Requirements Specification Document

Jump to bottom
VodkaSoul edited this page Dec 24, 2019 · 10 revisions

Requirement Specification

Project Scope

Background

This project focuses on the research and program development of solving linear equations from FEA (Finite Element Analysis) drawing on expertise from School of Software Engineering and College of Civil Engineering.

FEA (Finite Element Analysis) uses mathematical approximation to simulate real physical systems such as geometry and load conditions. With simple and interacting elements or units, a finite number of unknowns can be used to approximate an infinite unknowns in real system.

With the development of computer technology, the amount of computer storage is increasing, and the calculation speed is rapidly increasing. However, the scale of the problems to be solved is getting larger and larger, and the requirements for calculation storage and speed are becoming higher and higher. For example, there are hundreds of millions or more of unknown linear equations from problems such as finite element analysis of bridge structural mechanics and atmospheric prediction. In the field of Civil Engineering, the problems of concrete static analysis and bridge structure analysis of structural engineering, tunnel excavation in geotechnical engineering, rock blasting, artificial islands and access roads, and analysis of settlement of large oil storage tanks can all be concluded. Therefore, constructing efficient methods for solving discrete equations is an important part of computational mathematics for solving the finite element linear equations. At present, there are mainly two methods — direct solution method and iterative method.

For large matrices, the direct solution method requires a large amount of memory, and the amount of calculation is also very large. It usually takes several days or even months. Therefore, in practical applications, the iterative method is currently the main method for solving large-scale linear equations. It can make full use of the properties of the coefficient matrix including less memory occupation, easy calculation and simple program. In the basic iterative solution of linear equations, we mainly study how various basic iterative methods establish iterative schemes, prove iterative convergence conditions, adopt error estimates, and evaluate convergence speed.

In order to improve the calculation efficiency and shorten the calculation time, we also tried to use CUDA ™ (Compute Unified Device Architecture), a universal parallel computing architecture platform launched by NVIDIA®, to accelerate the solving of linear equations by using the idea of GPU parallel computing. For the further use of hardware acceleration algorithms, we explored the feasibility of GPU-accelerated deployment in Kubernetes to isolate GPU computing services and automatically load balance multi-GPU tasks.

Purpose

The purpose of the program is to study and investigate the program efficiency of multiple linear matrix iterative solutions, GPU parallel acceleration ideas, convergence conditions, etc. Based on the above survey, it is expected to provide simple, easy-to-use, and scalable program interfaces for various algorithms, and analyze the various algorithms at different accuracy requirements and operating efficiency at matrix size. For Jacobi Method and Conjugate Gradient Method, the CUDA platform is used to accelerate the above algorithms and analyze the acceleration efficiency. Finally, using these program interfaces, the system is expected to be capable of writing a simple front-end display page, reading the matrix file uploaded by the user, selecting the corresponding parameters for calculation, and displaying the graphs of the efficiency analysis of each algorithm on the display interface.

In summary, the goal of this project is to place equal emphasis on scientific research and development. General five stages in the scientific research process discovery, analysis, presupposition, research and exploration, and conclusion are included, and so do some methods in software engineering including requirements analysis and modeling, architectural design and detailed design. In the development process, we follow the software development process and principles, employ the process model to solve the chaos in the software process, and implement the software requirement definition and analysis, design, implementation, testing, delivery and maintenance at all stages.

Target Users

This target users of this project, which is a sub-topic of a scientific research topic, are mainly teachers from the College of Civil Engineering (that is, the project leader); after the final delivery of the product, the user can be a student of civil engineering majors, and all those engineers and students who have linear equations to solve.

Boundary of the Project

  • This project only involves the iterative solution of linear equations, not the direct solution of linear equations.
  • This project only provides the program interface of the linear equation solver. It does not provide other operators in the LAPACK linear calculation library such as the least-square method, eigenvalue solver, and matrix factorization.
  • This project solves both dense linear equations and sparse linear equations. Only the program interface of the conjugate gradient method is provided for solving sparse linear equations.
  • All iterative algorithms have convergence conditions. The coefficient matrix A is usually required to be a symmetric positive definite matrix or strictly diagonally dominant matrix, and it is difficult to give sufficient and necessary conditions in mathematical form. In order to improve the operation efficiency, this project does not detect the convergence conditions of the input matrix, but only checks whether the results converge after the algorithm is iterated.
  • This project supports the simultaneous operation of one or more CPU or GPU based iterative or unsteady iterative algorithms, but it is not possible to run the same or iterative algorithm at the same time.
  • This project supports users to upload their own matrices, and also supports users to upload execution files to expand the algorithm.

Use Case Analysis

UseCaseDiagram1

Tab 1. Initialize Solver Use Case
Use Case 1: Initialize Solver
ID: UC1
Actor: User
Description:
This use case allows users to initialize the linear solver, which contains some parameters to be appointed. In this phase, users need to choose matrix files or upload a new one, select algorithms, set parameters, and click the start button to start computation.
Pre-condition:
The user has entered the website.
Flow of Events:
  1. Include(Select Matrix Files)
  2. Include(Select Algorithms)
  3. Include(Set Parameters)
  4. Include(Start Computation)
Exceptions:
  1. If the size of the matrix in the selected matrix file is inconsistent with that of the matrix in parameters settings, the system will throw an error and inform the user to reset the size parameter or to reselect the matrix file.
  2. If there are no algorithms selected before the user presses the start button, the system will throw an error and inform the user to select at least one algorithm (either stationary iteraition or non-stationary iteration algorithm).
  3. If the user does not fill in some of the parameter field before he presses the start button, the system will throw an error and inform the user to fill in the required field.
Post-condition:
The website submits form to the back-end. The background solver acquires enough information and starts computation.
Tab 2. View Results
Use Case 2: View Results
ID: UC2
Actor: User
Description:
This use case allows users to view the analysis results generated by the system, including a line chart showing the comparison between the efficiency of the selected algorithms at different matrix size, as well as a bar chart illustrating the number of iterations of the selected algorithms.
Pre-condition:
The background program has computed the results of the selected algorithms, and the corresponding data has been delivered to the front-end webpage.
Flow of Events:
  1. The webpage obatains the statistical data auto-generated by the background program, including the time consumed for different algorithms at different matrix size and the number of iterations of different algorithms.
  2. The webpage generates a line chart and a bar chart to display the statistical data as mentioned above.
  3. The users can view the two charts at the left side of the website as soon as the calculation results come out.
Exceptions:
  1. If some of the selected algorithms cannot be iterated to convergence, some of the statistical data on the two charts will be missing accordingly.
Tab 3. Download Results Use Case
Use Case 3: Download Results
ID: UC3
Actor: User
Description:
This use case allows users to download the results of the calculation which is the solution vector of the linear system. The results are written in the txt files, and each file corresponds to the solution of each algorithm.
Pre-condition:
The background program has computed the results of the selected algorithms, and the results have been written in corresponding txt files.
Flow of Events:
  1. The user finds a record he needs in the results table.
  2. The user click the download button on the record as mentioned above.
  3. The user selects the path to save the file in the pop-up window of the web page and fill in the filename ha wants to rename the file.
  4. The user confirms the path and the filename, and click the confirm button to save the txt file.
Exceptions:
  1. If some of the selected algorithms cannot be iterated to convergence, the output file will be missing.
Tab 4. Delete Results Use Case
Use Case 4: Delete Results
ID: UC4
Actor: User
Description:
This use case allows users to delete the results of the calculation which has been saved by the user or is regarded as useless for the user.
Pre-condition:
The background program has computed the results of the selected algorithms, and the results have been written in corresponding txt files.
Flow of Events:
  1. The user finds a record he wants to delete in the results table.
  2. The user click the delete button on the record as mentioned above.
  3. The record disappears in the results table
Tab 5. Compute Results Use Case
Use Case 5: Compute Results
ID: UC5
Actor: Background Program
Description:
This use case describes the flow of the backgrond program computing the solutions of the linear systems, including reading data, executing particular algorithms, and outputing the solutions of equations as well as the statistical results.
Pre-condition:
The user has set the algorithms and corresponding parameters, and has submitted the form.
Flow of Events:
  1. Get the algorithms selected to be executed and the parameters set by users.
  2. Include(Read Matrix Data)
  3. Include(Execute Algorithms)
  4. Include(Output Results)
  5. Get the runtime statistical data.
Exceptions:
  1. If the matirx contains some errors, the background program will not crash, but exit with an error code, and will not generate any result.
Post-condition:
The output statistical data will be delivered to the data analysis component and the file save page.
Tab 6. Analyse Results Use Case
Use Case 6: Analyse Results
ID: UC6
Actor: Background Program
Description:
This use case illustrates the step of the background program analysing the statistical data generated by the analysis program of the background program. It is all about the time consumed to get solutions (including the CPU execution time and the GPU execution time). What's more, it also includes counting the number of the iterations of each algorithm.
Pre-condition:
The user has set the algorithms and corresponding parameters. The execution has been started.
Flow of Events:
  1. When the execution of particular algorithm starts, the timer starts, and each time the precision reduces 1/10, the timer returns the time consumed in this phase.
  2. At the same time, a global variable describing the number of iterations is incremented in each loop.
  3. When switching to another algorithm, repeat step 1-2, until all algorithms the user selected are executed.
  4. After all these have been done, aggregate the data and deliver it to the front-end.
Exceptions:
  1. If the matirx contains some errors or the background program runs into problems, the analysis program will not crash but exit with an error code, and will not generate any data.
Post-condition:
The analysis data will be delivered to the data analysis component.
.
Tab 7. Select Matrix File
Use case 7: Select Matrix File
ID: UC7
Actor: User
Description:
Select an input matrix file in the directory presented by the system.
Pre-condition:
Solver has been initialized. The input parameters like cpu/gpu and nums of executed methods have been chosen.
Flow of Events:
  1. View the folders presented by the system
  2. Choose a matrix file, it is the matrix to be solved.
Post-condition:
The matrix file is selected
Tab 8. Select Algorithms
Use case 8: Select Algorithms
ID: UC8
Actor: User
Description:
Choose a steady state iteration way from Jacobi(CPU/GPU), Gauss-Seidel, SOR or conjugate Gradient(CPU/GPU)
Flow of Events:
  1. Choose a tab from Steady Iteration and Conjugate Gradient
    1. Steady Iteration :Variant 1a
    2. Conjugate Gradient:Variant 1b
Exceptions:
  1. If the process of iteration doesn't end while the number of iterations exceeds the upper limit, we assume that Gauss-Seidel Iteration doesn't converge on these linear equations. The system will inform the user this non-convergent situation.
Variant 1a:
  1. Choose one or more methods from Jacobi(CPU/GPU), Gauss-Seidel and SOR
Variant 1b:
  1. Choose one or more methods from CPU Conjugate Gradient and GPU Conjugate Gradient
Post-condition:
The alogrithms are selected and waited to be executed.
Tab 9. Set Parameters Use Case
Use case 9: Set Parameters
ID: UC9
Actor: User
Description:
Set parameters such as matrix dimension, result precision and so on.
Pre-condition:
Solver has been initialized.
Flow of Events:
  1. Set coefficient matrix dimension.
  2. Set target precision.
  3. Set relaxation parameter for SOR.
Exceptions:
  1. If matrix dimension is not integer or less than 0, the system will inform dimension error of the user.
  2. If matrix dimension is less than 0, the system will inform dimension error of the user.
  3. If relaxation parameter is smaller than 0 or larger than 2, the system will inform relaxation parameter error of the user.
Post-condition:
Parameters have been set.
Tab 10. Start Computation Use Case
Use Case 10: Start Computation
ID: UC10
Actor: User
Description:
This use case allows users to click start button to start computation.
Pre-condition:
The user has filled in all required information about the equations.
Flow of Events:
  1. User clicks on the start button.
  2. The parameters and matrix file would be upload to the server.
  3. The back-end would call corresponding algorithm programs to solve.
Post-condition:
The back-end would gain the result and return it to the web.
Tab 11. Read Matrix Data
Use case 11: Read Matrix Data
ID: UC11
Actor: Background Program
Description:
Set parameters such as matrix dimension, result precision and so on.
Pre-condition:
Solver has been initialized and matrix dimension has been set.
Flow of Events:
  1. Get matrix dimension.
  2. Read matrix data from txt file.
Exceptions:
  1. If matrix dimension doesn't match the real one, the system will inform dimension error of the user.
Post-condition:
Matrix is ready.
Tab 12. Execute Algorithms
Use case 12: Execute Algorithms
ID: Background Program
Actor: User
Description:
Execute chosen algorithms and get results.
Pre-condition:
Solver has been initialized. Coefficient matrix has been uploaded. All parameters have been set and met the requirements.
Flow of Events:
  1. Initialize the solution of linear equations before the first interation.
  2. Initialize the value of current error.
  3. Set the upper limit for the number of iterations.
  4. Execute Iteration until current error is less than pre-defined precision.
Exceptions:
  1. If the process of iteration doesn't end while the number of iterations exceeds the upper limit, we assume that appointed iteration doesn't converge on these linear equations. The system will inform the user this non-convergent situation.
Post-condition:
Result with specified precision will be stored and waiting to be output.
Tab 13. Output Result Use Case
Use Case 13: Output Result
ID: UC13
Actor: Background Program
Description:
This use case shows how web gain the results.
Pre-condition:
The algorithm programs on the server have finished the iterations.
Flow of Events:
  1. The algorithm programs save the solution into txt file.
  2. The back-end detects that the solution file is generated and send message and the download link to the web.
  3. The web shows the downloadable solution file list.
Tab 14. Upload Matrix Files
Use case 14: Upload Matrix Files
ID: UC14
Actor: User
Description:
The User upload a matrix file from local directory.
Pre-condition:
The users can not find the matrix file in the directory presented by the system.
Flow of Events:
  1. Choose the specific directory in the user's direcotry
  2. View the matrix files
  3. Choose the matrix file to upload.
Exceptions:
  1. If the file doesn't meet the correct format(not .txt),the procedure will go wrong.
Post-condition:
The maxtrix file is selected
Tab 15. Execute Gauss-Seidel Iteration Use Case
Use case 15: Execute Gauss-Seidel Iteration
ID: UC15
Actor: Background Program
Description:
Execute Gauss-Seidel Iteration until get results with specified precision.
Pre-condition:
Solver has been initialized. Coefficient matrix has been uploaded. All parameters have been set and met the requirements of Gauss-Seidel.
Flow of Events:
  1. Initialize the solution of linear equations before the first interation.
  2. Initialize the value of current error.
  3. Set the upper limit for the number of iterations.
  4. Execute Gauss-Seidal Iteration until current error is less than pre-defined precision.
Exceptions:
  1. If the process of iteration doesn't end while the number of iterations exceeds the upper limit, we assume that Gauss-Seidel Iteration doesn't converge on these linear equations. The system will inform the user this non-convergent situation.
Post-condition:
Result with specified precision will be stored and waiting to be output.
Tab 16. Execute SOR Iteration Use Case
Use case 16: Execute SOR Iteration
ID: UC16
Actor: Background Program
Description:
Execute SOR Iteration until get results with specified precision.
Pre-condition:
Solver has been initialized. Coefficient matrix has been uploaded. All parameters have been set and met the requirements of SOR.
Flow of Events:
  1. Initialize the solution of linear equations before the first interation.
  2. Initialize the value of current error.
  3. Set the upper limit for the number of iterations.
  4. Execute SOR Iteration until current error is less than pre-defined precision.
Exceptions:
  1. If the process of iteration doesn't end while the number of iterations exceeds the upper limit, we assume that SOR Iteration doesn't converge on these linear equations. The system will inform the user this non-convergent situation.
Post-condition:
Result with specified precision will be stored and waiting to be output.
Tab 17. Execute Jacobi Iteration Use Case
Use Case 17: Execute Jacobi Iteration
ID: UC17
Actor: Background Program
Description:
This use case shows how the back-end executes Jacobi Iteration.
Pre-condition:
The algorithm programs have got all the parameters and matrix.
Flow of Events:
  1. The back-end receive the command to execute:
    1. Jacobi CPU Version :Variant 1a
    2. Jacobi GPU Version :Variant 1b
Variant 1a:
  1. The program keep sequentially iterating in cpu until the error reachs the precision requirements.
Variant 1b:
  1. The program would detect all the devices(GPU),and choose the best device to handle the problem.
  2. The program would allocate memory for matrix and variables on GPU.
  3. The program keep sequentially iterating in cpu , and compute the solution elements in parallel , until the error reachs the precision requirements.
Exceptions:
  1. If the iterations reach the preset maximum value, the progarm would stop.
Post-condition:
The solutions would be saved into txt file.
Tab 18. Execute Conjugate Gradient Iteration Use Case
Use Case 18: Execute Conjugate Gradient Iteration
ID: UC18
Actor: Background Program
Description:
This use case shows how the back-end executes Conjugate Gradient Iteration.
Pre-condition:
The algorithm programs have got all the parameters and matrix.
Flow of Events:
  1. The back-end receive the command to execute:
    1. Conjugate Gradient CPU Version :Variant 1a
    2. Conjugate Gradient GPU Version :Variant 1b
Variant 1a:
  1. The program keep sequentially iterating in cpu until the error reachs the precision requirements.
Variant 1b:
  1. The program would detect all the devices(GPU),and choose the best device to handle the problem.
  2. The program would allocate memory for matrix and variables on GPU.
  3. The program keep sequentially iterating in CPU , and compute the solution elements parallelly in GPU , until the error reachs the precision requirements.
Exceptions:
  1. If the iterations reach the preset maximum value, the progarm would stop.
Post-condition:
The solutions would be saved into txt file.

Software Engineering, Fall 2019 & Software Test, Spring 2020.

It is a collaborative and interdisciplinary project drawing on expertise from School of Software Engineering & College of Civil Engineering, Tongji University.

Xlab-k8s-gpu

Home

Software Specification

Design

Project Feasibility

Solution of Equations

K8s Environment Config

Clone this wiki locally