Source-linked AI summary
The Multithreaded version of FORM
M. Tentyukov, J. A. M. Vermaseren
TL;DR
FORM’s large-expression workloads motivate parallel execution on shared-memory computers. The paper presents TFORM, which uses Posix threads and preserves compatibility with most existing programs. Typical running-time improvement is 1.7× on two processors and slightly above 3× on four processors, although bottlenecks and some dollar-variable uses limit benefits.
Problem
FORM’s large symbolic calculations increasingly require computer power, motivating effective use of multiple processors on shared-memory computers.
Method
TFORM adapts FORM for shared-memory parallelism using Posix threads, with expression distribution, merging, caching, and variable handling designed for concurrent execution.
Results
TFORM handles existing FORM 3.1 programs in principle, with better running-time improvement on computers with a limited number of processors and more complicated programs.
Takeaways & Limitations
For a small number of processors, the current TFORM version is more than adequate, while very large processor counts benefit only for special problems.
Takeaways & Limitations
Some dollar-variable uses force affected modules into sequential mode, and sorting can suffer severe filesystem contention on multiple processors.
Abstract
from arXiv · showhide
We present TFORM, the version of the symbolic manipulation system FORM that can make simultaneous use of several processors in a shared memory architecture. The implementation uses Posix threads, also called pthreads, and is therefore easily portable between various operating systems. Most existing FORM programs will be able to take advantage of the increased processing power, without the need for modifications. In some cases some minor additions may be needed. For a computer with two processors a typical improvement factor in the running time is 1.7 when compared to the traditional version of FORM. In the case of computers with 4 processors a typical improvement factor in the execution time is slightly above 3.
1 Introduction
FORM targets large symbolic expressions, and TFORM extends it to shared-memory parallel processing with pthreads. The design addresses thread safety, expression distribution and merging, file-access contention, and dollar-variable conflicts while aiming to preserve existing programs.
- FORM has supported large symbolic calculations, especially in quantum field theory, for more than 17 years.The paper attributes major advances in field-theory calculations to FORM and states that several spectacular calculations depended on it.
- TFORM uses Posix threads to exploit more efficient communication on shared-memory computers.Pthreads share memory, follow strict standards, and are widely available across operating systems.
- FORM can be parallelized because its operations act on individual terms, while variable administration must remain independent of processing order.The parallel design must coordinate information exchange whenever expression terms are redistributed or recombined.
- Parallel execution has bottlenecks when expressions are read and distributed, then sorted, merged, and written back to disk.The final merge is performed by a single processor, so bottleneck efficiency limits total running-time improvement.
- Simultaneous file access can cause waiting and disk traffic jams, making four-processor execution slower than single-processor execution in some cases.Separate caching systems are intended to reduce waiting, but later sorting stages can still create severe contention.
- The tests use existing single-processor programs with minimal or no changes, and speedup depends on programming style, sorting, and external-file use.The measured quantity is wall-clock running time on an otherwise lightly loaded computer.
2 Cleaning up the internals of the FORM sources
TFORM required FORM’s internals to distinguish shared and thread-private state, make routines thread-safe, and serialize file access. These changes largely preserve a common source base but slightly reduce average single-processor performance.
- Thread safety: Thread-safe routines must prevent simultaneous calls from unintentionally sharing temporary data.A shared ScratchArray would let concurrent Multiply instances overwrite one another, motivating strict separation of common and private variables.
- Thread-private state: FORM avoids extensive restructuring by placing each thread’s private state in a separate structure addressed through pointer B.Private copies of the N, R, and T substructures are allocated per thread, while remaining common data stays in structure A.
- Performance impact: The cleanup changes affect nearly all code and make TFORM slightly slower on average than the sequential version.Rare cases were observed in which single-processor TFORM was slightly faster than the sequential version using the original macro definitions.
- File access: Parallel file access requires locks and placing file positioning immediately beside file access to minimize lock duration.The sequential assumption that one routine could position a file for another no longer holds in parallel execution.
- File access: Stored-expression caching was redesigned, and the sequential version also benefits when programs use stored expressions intensively.The caching change is an implementation improvement shared by both execution modes.
- Source maintenance: Maintaining one source-code base is easier because one parameter selects sequential or multithreaded compilation.Related cleanup changes therefore affect all FORM versions rather than requiring separate source trees.
3 The parallelization
TFORM parallelizes eligible FORM module execution with a master thread and worker pool, distributing expression terms while coordinating synchronization, sorting, and shared variables. Its effectiveness depends on workload balance and file-system behavior, with several cases requiring sequential execution or careful program organization.
- Thread model: TFORM starts one master thread and N worker threads in a thread pool, with module execution eligible for parallelization.Workers allocate private memory, then sleep while the master preprocesses and compiles modules before parallel execution begins.
- Work distribution: The master distributes expression terms to workers in buckets, using signals and spare buckets to reduce waiting.The default bucket size is 500 terms, and the total number of buckets is twice the number of workers.
- Work distribution: Load balancing can steal terms from workers’ buckets, but it fails when a single term consumes most of the CPU time.A new expression begins as one term and expands inside the module, so such a module cannot use the parallelization effectively.
- Sorting: Concurrent file-based sorting initially made a four-processor test take more than four times the single-processor real time, whereas the selected method reduced it to slightly over half.The effect depends on file-activity organization, sorting-buffer size, cache size, and computer, and did not occur in the other examples.
- Sorting: Final sorting uses worker output in the master’s sort buffers, where the master merges sorted results under a shared data-block system.The selected design removes worker scratch files and permits simultaneous sorting when possible.
- Shared variables: Dollar variables can cause conflicts between workers; unsupported uses make TFORM switch affected modules to sequential mode so old programs continue to run.Private values are combined into a common value at module end when specified through ModuleOption.
4 The performance
TFORM runs existing FORM programs in parallel with little modification, but performance depends on workload, buffering, and the amount of work assigned to the master thread.
- Parallel execution: Existing FORM programs can run in parallel after modifications, except execution-time dollar-variable assignments lacking ModuleOption statements remain sequential.The -w argument specifies the number of worker threads; omitting it or setting it to zero uses only the master thread.
- Chromatic polynomials: Chromatic-polynomial tests use a FORM example program with pattern matching and polynomial arithmetic across computers with 2, 4, and 32 processors.The benchmark includes simple and bigger lattices, with additional runs using smaller sorting buffers.
- Chromatic polynomials: Nearly simultaneous disk operations reduce performance, especially when larger lattice calculations require worker-specific sort files.Smaller buffers cause more disk operations, while the effect varies between computers and file systems.
- Mincer: 3.3 is a high improvement factor for Mincer on four processors, despite 5%–10% multithreading overhead and master-only processing periods.The theoretical limit is about 3.6 on four processors; the tests used unchanged Mincer code for three-loop non-planar diagrams.
- Scaling limits: Saturation appears as worker counts increase because final sorting and data distribution increase the master’s workload and can make threads wait.On one four-processor computer, the optimum is 4 workers; with 32 workers, merging 32 streams requires about 5 comparisons per term.
- Multiple zeta values: 3.49 is the record improvement factor for the weight-10 multiple-zeta-value calculation on four processors, while simpler equations benefit less from parallelization.Parallel efficiency is better when GCD calculations remain local or private, whereas master CPU time limits scaling as processor counts increase.
5 Conclusions
TFORM can handle, in principle, all programs running on FORM 3.1, while generally improving parallel execution for more complicated programs and small processor counts. Its scalability is limited by master-thread work and sorting bottlenecks, with further optimization left for future versions.
- TFORM can handle in principle all existing programs that would run on version 3.1 of FORM8.
- More complicated programs generally obtain better improvement from TFORM, while small processor counts are considered adequately supported.
- Extensive changes may have introduced bugs that had not yet been detected.
- Large processor counts experience strong saturation because the master thread must perform increasing amounts of work.The authors identify reducing master-process load, especially during final sorting stages, as the main future improvement.
- A sorting tree retains a program-dependent bottleneck because one compare per term must occur inside a single thread.
- Only special problems currently benefit from very large processor counts, whereas the current TFORM version is more than adequate for small processor counts.