CS-Map RFC 5 - Mutli-thread SUpport Upgrade

This page contains an change request (RFC) for the CS-Map Open Source project. More CS-Map RFCs can be found on the RFCs page.

Status

RFC Template Version	(1.0)
Submission Date	Thu Jun 16 12:57:21 2011
Last Modified	Norm Olsen Timestamp
Author	Norm Olsen
RFC Status	draft
Implementation Status	pending
Proposed Milestone	13.2
Assigned PSC guide(s)
Voting History	(vote date)
+1
+0
-0
-1
no vote

Overview

While there exists some code in CS-MAP addressing the multi-thread safety issue, it is essentially commented out, was Microsoft specific, and relied on a feature of Microsoft which the best I can remember didn’t work anyway. Thus, while it can be done now, using CS-MAP in a multi-threaded environment must be done carefully, and usually so carefully that no benefit is derived there from. This RFC, proposes to remove the existing non-functional and commented out code (csThread) and add features which address the multi-thread safety issue in a more general, platform independent manner. The result may not necessarily be a completely thread safe library, but a significant improvement in CS-MAP’s ability to perform in the multi-thread environment.

Terminology

We shall use the term reentrant to refer to an object whose use is multi-thread safe. That is, a pointer to a reentrant object can be duplicated without limit and such duplicate pointers passed to additional threads without limit, without any negative effect on the results produced by the object or its performance. For the purposes of this proposal, please think of conversions (i.e. projective operations) and transformations (i.e. datum shift operations) as being either reentrant or non-reentrant.

Motivation

Even the least expensive machines on the market today are (at a minimum) dual core. In server environments where CS-MAP is used, even more multi-processor capability is available. The current structure of CS-MAP pretty much requires that conversions be limited to a single thread. Enabling the reliable use of multiple threads in a large conversion effort (read Cloud Computing) would be greatly appreciated by many developers.

Proposed Solution

No changes are proposed for existing interfaces or core functionality, while some new functionality is proposed and will be exposed. Two separate phases of solution are proposed, as each is essentially independent of the other and can be implemented, tested, documented, and released independently of each other. Additionally, the proposal is such that the implementation of Phase Two can be spread out over time, and over several releases, without negative side effects.

The proposed solution addresses the reentrancy of the actual coordinate conversion/transformation methods and algorithms only. All methods, objects, and algorithms related to conversion/transformation object construction, dictionary meta data, dictionary maintenance, UI support, etc. etc. will remain as. That is, by-in-large non-reentrant.

Most all of the conversions and many of the transformations within CS-MAP are inherently reentrant and have been for some time. In Phase One of this proposal, we simply provide information to the developer as to the reentrant behavior of any given conversion and/or transformation, or combination thereof. Given this information, a developer can determine if using multiple threads is safe and/or if an exclusive lock needs to be applied to a specific portion of the entire conversion process.

Phase One

Most all of the conversions and many of the transformations within CS-MAP are inherently reentrant and have been for some time. In Phase One of this proposal, we simply provide information to the developer as to the reentrant behavior of any given conversion and/or transformation, or combination thereof. Given this information, a developer can determine if using multiple threads is safe and/or if an exclusive lock needs to be applied to a specific portion of the entire conversion process.

Implementation of Phase One will be accomplished by adding a new property to the projection flags element of the projection table. Using this feature, each projection will be classified as being reentrant or non-reentrant. (Currently, only the OSGB variations of the Transverse Mercator which use the ordnance survey grid tables are known to be non-reentrant). A similar feature was designed in the the Geodetic Transformation table, but is as yet unused. This feature will be implemented and each geodetic transformation method classified in the table as being either reentrant or non-reentrant.

Implementing the API's for this feature is then a matter of extracting the conversion/transformation method and extracting the reentrancy bit from the properties flag word of the appropriate table.

Phase Two

Those CS-MAP conversions and transformations which are not reentrant are usually that way due to the heritage of CS-MAP (the days of the 640KB PC and no more than 8 files open at one time) and the level of resource consumption which would be necessary to achieve reentrant status. In Phase Two of this proposal, all non-reentrant conversions and transformations for which reentrancy can be achieved without unreasonable additional resource consumption will be recoded to achieve reentrancy.

Hubris might lead one to believe that the entire library could be re-written to achieve complete reentrancy. While this is indeed the expected result, this proposal retains Phase One as necessary to:

• insure that exceptions are not encountered, and to
• prevent a reentrancy requirement from precluding valuable future additions to the algorithmic repertoire of the library.

Currently, the geocentric and multiple regression transformation methods are considered reentrant. All of the grid file interpolation methods are considered to be non-reentrant. Grid file interpolation techniques tend to be non-reentrant as the code typically buffers data from the grid file in the transformation object for performance reasons. Unless the file is buffered in its entirity, the object becomes non-reentrant. An object that does no buffering at all would be reentrant, but would probably suffer a performance hit. Thus, completing Phase Two will require some non-trivial engineering efforts.

Implications

For certain transformations, converting to reentrant status may incur a performance degradation. In such cases where this reduction in performance is noticeable, it is considered likely that a reasonable increase in the size of the memory resources consumed will appropriately compensate. If such is not the case, the implementers shall then choose to either accept the performance hit or mark the transformation as non-reentrant depending upon the degree of the performance degradation and the “popularity” of the specific conversion/transformation involved.

Test Plan

Normal regression testing will apply to insure that existing numerical results are preserved. Additionally, a multi-core specific test module shall be developed which, given a table of test cases specifically constructed to include most (if not all) conversions and transformations (directly or indirectly), shall:

• Construct all the CS-MAP conversion and transformation objects necessary to perform all conversions. This will typically consist of a source cs_Csprm_ object, a cs_Dtcvt_ object, and a target cs_Csprm_ object.
• Pointers to such conversion and transformation objects shall be duplicated as necessary to fully populate the test table such that only one instance of any equivalent conversion/transformation object exists.
• A function capable of performing any conversion given a pointer to a table entry (which includes the three pointers identified above) will be written.
• The host test application will create a new threads and thus cause the execution of the test conversion function with the pointers obtained from the above described table.
• The host test application will cause 16 threads to perform the same tests using the same objects concurrently.
• This test shall for a specified amount of time, the default value will be 20 seconds. It is expected that each of the 16 threads will execute, on average, 20 times in this period of time.
• In the event of an error, the test application lists the indicate the specific test conversion which produced the failure.

It is expected that this test facility will be implemented using the environment of the MeatCRS’s OsGeo siblings, MapGuide, as the MapGuide environment is more readily adaptable to multi-threaded applications.

Funding/Resources

Funding and developer resources to be provided by Autodesk.