Yong Jiao's Blog about Technology and Life

Simple Comparisons on some In-Memory Data Grids

2014-06-27T14:00:00.001-04:00

Fetures	Feature Description	GemFire7	Coherence3.7	Infinispan5	Gigaspaces7	Notes
1. topologies	peer-peer; client-server	High	High	High	High
2. cross-site / WAN replication	datacenter-datacenter; region-region	High	Low	Med	High	Coherence support by incubator "Push replication"; Infinispan basic support in V5.2
3. read-most scalability	via replication	High	High	High	High
4. write-most scalability	via partitioning and replication between primary and backups	High	High	Med	High
5. high availability / HA	via replication and persistence into disk (DB)	High	High	High	High
6. asychronous replication	useful for slow changing data and WAN replication	High	Med	High	High	Coherence support by incubator "Push replication";
7. partition rehashing	consistent hashing to reduce data relocation	High	High	High	High	all seem to use consistent hashing-like algorithms
8. dynamic clustering	adds or loses nodes	High	High	High	Med
9. updating among partition backups	master-backup: less deadlock prone and IO master-master/update anywhere: more dealock prone and IO	High	High	Low	High	Infinispan only has master-master that incurs deadlock for slow network and large caches
10. cache loader and writer	2 application interfaces: loades data from DB and saves data into Cache. With cache loader and writer, applications only need to interace with Cache!	High	High	Med	High	Infinispan writers only support JPA, not JDBC or Hibernate!
11. read-through and read-ahead	populates cache with DB in batch mode	Med	High	Med	High	no prefetch/batch support from Gemfire and infinispan
12. write-through and write-behind	persists cache into wherever they were loaded.write-behind persists data asynchronously	High	High	Med	High
13. event notification	Cache also works as a messaging and parallel processing bus like JMS/MDB	Med	Med	Med	High
14. continous querying	register contents-based interests with Cache and receive updates continously.	High	High	Low	High
15. cache querying	SQL like query: not only searches based on key matching	High	High	Low	High
16. locking and tx	JTA (global tx) and ACID properties	High	High	Med	High
17. off-heap	puts cache data off Java heap so that GC pause time is reduce!	Low	High	Low	Low
18. key affinity / colocation	colocates related cache objects on the same partition to reduce IO	High	High	High	High
19. customized partitioning	puts cache into specific cluster node to bypass cache hashing algorithm	High	Low	Med	Low
20. synchronous requests like RFQ	synchronou requests should go through the same partition routing as asynchrous messages.	Low	Low	Low	High
21. API	Map,Restful and appropriate interfaces	Med	Med	Med	High
22. language bindings	Java, C++ etc	Med	Med	Med	High
23. map-reduce / scatter-gather	submits aggregation tasks to run across multiple or all cluster nodes	High	High	High	High
24. monitoring	monitor the health of clusters	High	Med	Med	High
25. J2EE (JMS,Web, Remoting)	how much J2EE? to support?	Low	Low	Low	High
26. migration effort	how to migrate to a different cache production in a J2EE app. server	High	High	High	Low	GigaSpaces is an app. server

JMS Connection and Session on WebSphere MQ 7.1

2014-06-23T13:55:00.001-04:00

The difference between JMS API's Connection and Session will probably confuse many naive developers. Their performance implications will only make things worse.
This is primarily because we are used to thinking connection and session are the same and can be used interchangeably to represent a unique single-threaded conversation between a server and a client. This is indeed the case for DB servers and clients.

The basic idea of JMS API's connection and session is to first create a top level heavyweight physical connection, then several lightweight sessions / logical connections under the only physical connection.
Because of the connection's heavyweight nature, we usually pool them just like DB connection pooling. We hope the connection can create lightweight sessions very fast and service its session operations (sending, receiving, tx etc) efficient by multiplexing them through its only physical connection.
Add to this, the following Spring configures supports caching a single JMS connection and multiple sessions:

<bean id="cachedConnectionFactory" class="org.springframework.jms.connection.CachingConnectionFactory"
p:targetConnectionFactory-ref="myConnFactory" p:sessionCacheSize="10"/>

However the JMS specification doesn't say how the MOM vendors should implement connections and sessions. For earlier WebSphere MQ versions before 7, each JMS session actually also represents a brand new physical connection / channel instance just like a JMS connection.
MQ version 7 introduces the so called "sharing conversations" which allows a configurable number of JMS connections and sessions (both represent conversations in MQ terms) to share a single physical connection / channel instance.
The number of conversations that can be shared across a single physical connection / channel instance is determined by the WebSphere MQ channel property SHARECNV. The default value of this property for Server Connection Channels is 10. A value of 0 or 1 basically disables the sharing.
In order to use this feature, your client side JMS connection factory also need to enable property
SHARECONVALLOWED.
For example, assuming SHARECNV is 10, you created 5 connections and 15 sessions (it doesn't matter which connections created which sessions from sharing perspective), the total physical connections needed is (5+15)/10=2
For more information, you refer to this page.

If you are developing a low latency and high performance application, you must know how to tune JMS connections and sessions on your MQM vendor.

How to Create Sessions quickly?
If you use the previous Spring config, you should estimate the maximum sessions you needs and then pre-populate some of them based on the SHARECNV value. Otherwise some session creations will be as slow as creating a new physical connection.
How Many Connections to Create?
Due to the multiplexing nature, if most of the multiplexed sessions under a connection are busy most of the time, you should move those busy sessions to new connections. Of course, you should manage connections using pooling such as retrieving them from an application servers.

Class Loading Issue when Running Gemfire 7.x OQL in Weblogic 10.3.x

2014-05-29T14:52:00.001-04:00

I have a very simple OQL like "SELECT * FROM /FxLimitsRegion" that ran successfully in my unit/integration test. But I got the following exception when trying to run it inside my WebLogic EAR (our Gemfire cache and Weblogic application server run in the same JVM):

com.gemstone.gemfire.cache.query.QueryInvalidException: Syntax error in query: Invalid class or can't make instance, com.gemstone.gemfire.cache.query.internal.parse.ASTSelect
    at com.gemstone.gemfire.cache.query.internal.QCompiler.compileQuery(QCompiler.java:80)
    at com.gemstone.gemfire.cache.query.internal.DefaultQuery.(DefaultQuery.java:156)
    at com.gemstone.gemfire.cache.query.internal.DefaultQueryService.newQuery(DefaultQueryService.java:107)
    at com.gemstone.gemfire.internal.cache.LocalDataSet.query(LocalDataSet.java:129)
    at com.jpmorgan.gcrm.sef.business.cache.impl.SEFCacheManagerGemfireImpl.queryPartitionedRegionLocally(SEFCacheManagerGemfireImpl.java:187)
    at com.jpmorgan.gcrm.fno.business.datamanager.impl.FxDataManager.selectActiveFxLimits(FxDataManager.java:57)
    ... 13 more
Caused by: java.lang.IllegalArgumentException: Invalid class or can't make instance, com.gemstone.gemfire.cache.query.internal.parse.ASTSelect
    at antlr.ASTFactory.createUsingCtor(ASTFactory.java:251)
    at antlr.ASTFactory.create(ASTFactory.java:210)
    at com.gemstone.gemfire.cache.query.internal.parse.OQLParser.selectExpr(OQLParser.java:1090)
    at com.gemstone.gemfire.cache.query.internal.parse.OQLParser.query(OQLParser.java:217)
    at com.gemstone.gemfire.cache.query.internal.parse.OQLParser.queryProgram(OQLParser.java:115)
    at com.gemstone.gemfire.cache.query.internal.QCompiler.compileQuery(QCompiler.java:76)

The class "com.gemstone.gemfire.cache.query.internal.parse.ASTSelect" to load was included in the gemfire.jar in my EAR. So the exception seems to be confusing in the beginning.
From the above stack trace, you can see it relates to the ANTLR jar. Both my EAR and Weblogic itself have ANTLR. But my EAR uses version 2.7.7 while Weblogic 10.3.2 uses a pretty old version.
So we need to know which ANTLR version was used. Here is the call workflow:
1. my EAR thread issued a OQL ->
2. Gemfire found ANTLR to parse the OQL to AST ->
3. ANTLR tried to load Gemfire class "com.gemstone.gemfire.cache.query.internal.parse.ASTSelect"

By default, Step2 found the Weblogic ANTLR by the Weblogic system class loader. But the Gemfire class is in the child EAR classloader. So Step 3 threw the exception.
If we can tell Weblogic to use my EAR ANTLR, the exception should be gone. In order to do so, I just added the following excerpt to your weblogic-application.xml:
         <prefer-application-packages>
               <package-name>antlr.*</package-name>
         </prefer-application-packages>
New version of ANTLR changed to load classes from the thread context class loader by default which was the EAR classloader in my case. So if the Weblogic had new version of ANTLR, the exception should have not been there.

Cache Replicatio and Partition -- How to Scale linearly using Cache Listeners?

2013-10-20T19:08:00.000-04:00

1. The System in Question

I am working on a trade (credit default swap and interest rates swap) processing system that calculates the client's limit exposures in real time.
The system consists of a 4-node WebLogic cluster that retrieves trades from an IBM clustered queue using MDB and puts trade data into a distributed cache / IMDG.
Suppose each node in the cluster has the following capacity:

Here is the cluster that doesn't scale linearly:

2. Pros and Cons of the System

Pros

Even distribution of trade processing because any trade can be processed at any node and we use master-master/update-anywhere replication cache;
Scales reads linearly (the metric in green) because reads take place locally;
Easy application design because there is no customized trade routing algorithm;

Cons

Writes can't be scaled linearly (the metric in red) because of the cluster-wide replication and synchronization between nodes;
The cluster wide total memory is limited to a single node (the metric in red);
Be timeout and deadlock prone because a distributed locking / synchronization is needed across nodes if they process the same client's trades simultaneously;

3. How to Scale linearly?

Linear scalability can be achieved only when each node can process trades (nearly) independently.
For reads, you can achieve linear scalability with replication;
For writes, you must keep the data replication effort constant and eliminate distributed locking / synchronization. So partition is the only choice.
An application usually has both reads (such as reference data) and writes (such as limit exposures in my case).
So you should replicate reads unless they are huge (if so, you have to partition them and still use near / local cache for the frequent used subset).
You should partition writes in order to keep the replicas of primaries constant and to avoid using any distributed locking.

4. Scales the System linearly using Cache Listener-based Routing

So for my trading application, I just need to replace replication for partition for writes in order to scale linearly.
One naive implementation is to have a separate routing node between MQ and the WebLogic cluster and partition trades for the same client to the same nodes using a simple hash algorithm.
There are 2 big problems here. One is that the trade was routed to some node that may not have the partitioned cache because the distributed cache and the routing node may have different partition algorithms (most likely). If so, remote network calls are needed.
The other is that the simple hash algorithm can't deal with dynamic cluster. This is why most IMDG employ consistent hashing. If you want to use consistent hashing, the amount of work and complexity will overwhelm most application level developers.

All distributed cached / IMDG (Infinispan, Gemfire and GigaSpaces etc) support distributed cache listeners. When you put data into a partitioned cache, IMDB will automatically route the data to some primary partition member based on whatever hashing algorithms it internally employs, and only the listeners registered on the primary will be invoked and the listener will gets trades only on its local primary (not from other remote primaries).
We can use the distributed cache listener to do our routing. Here is the partitioned version:

4.1 Notes

We only have one replica per one primary for space reason. You should decide the number of replicas based on the balance between HA and write performance. In order to have reasonable HA and durability, at least 2 backups across different racks are common practice;
For space reason, the diagram only generally says primary cache. Usually more than 1 different caches need partitioning. If so, they should col-locate on the same node in order to eliminate remote network calls. In my case, we col-locate data based on client ID;
The “Cache Message Bus” not only works as a parallel routing bus (put and take), but also as a cache bus for replication. The figure doesn’t connect the replication to the bus for space reason;
There is no deadlock or lock timeout issue across nodes because all updates for a client are coordinated / locally synchronized by the primary node;

4.2 Workflow

Any trade listener (MDB hosted by the WebLogic cluster) can get any post trade. It barely parses trades to extract client ID, and calls the partition strategy to route trades to some partition member. Thanks to the WebLogic cluster, this solution possesses load balancing and HA;
We use client ID as the partition strategy. As soon as the listener extracts out the client ID, it just calls the cache PUT operation to automatically route trades based on its internal partition algorithm (Consistent Hash is commonly used);
Only the cache listener on the primary takes the trades that were routed there (no remote takes from other primaries). Because the listener runs in the same thread of the PUT operation, it submits the retrieved trades to a thread pool for asynchronous execution in order not to delay invoking PUT;
The executor processes trades that should only incur local cache operations (GET from the primary and PUT to backups). If it incurs remote operations (from other partition), it means you didn’t col-locate data properly or didn’t replicate needed reference data;

Most developers knows how to use IMDG for data caching, but are not familiar with IMDB's listener capability (or event processing at an even higher level). On one hand, IMDB listeners are powerful and easy to understand just like DB triggers. On the other handle, they are not as robust as JMS / MDB.
For example, MDB provides threading pool and different level of delivery guarantee such as once and only once delivery.
However in my case, we only use the IMDG listener lightly: as soon as the listener gets the trades, it submit them to an executor pool. If something goes wrong between PUT and listener TAKEN, the PUT will fail and you can employ retry logic or there delivery logic there.

Lastly, I must mention GigaSpaces XAP that provides the listener based routing naturally and natively. You can get many functions such as MDB-like threading pool out of the box. If you start a new project, you should seriously consider GigaSpaces XAP.

Cache Replicatio and Partition -- Basic Concepts and Pros and Cons

2013-10-13T21:10:00.000-04:00

If you are a lead in your development team and only few members have IMDG experience, it is absolutely necessary to educate your team with basic concepts. Otherwise you will probably waste too much time on endless clarification and explanation.
For example, when I recommended partition, I was told I would lose replication. They didn't realize that the partition scheme allows a configurable number of replicas for the primaries.

Here are slides I used for education purpose.

Assumptions
- The cluster has 4 nodes each of which has the same read, write and memory metrics as follows:
- How a metric changes as the cluster grows?
  The metric in red decreases at node level, either remains constant or increases less linearly at cluster level.
  The metric in green remains constant at node level, and increase linearly at cluster level.
- Replication is synchronous.
- There is only one replica in partition.
Replication
Partition
Replication pros and cons

Pros
- HA
- Scales reads linearly
- Asynchronous replication
Cons
- Can NOT scale writes linearl
- Cluster memory capacity equals a single node memory capacity
- Conflict resolution for asynch. replication
- Global locking for synch. replication (deadlock prone)
Usage
- Small cluster
- Small capacity
- Read-most
Partition pros and cons

Pros
- Scales writes linearly
- Scales memory linearly
- Configurable HA
- Local lock only. Synch. replication only. No Conflict resolution
Cons
- Can NOT scale reads linearly
- No asynch. replication
Usage
- Large cluster
- Large capacity
- Write-most

Connecting to Websphere MQ from Weblogic using Certificate

2013-03-27T22:03:00.000-04:00

Here is the requirement: we need to connect to a remote Websphere MQ sever (v7.x) from a Weblogic servier (v10.3) using a certifcate by configuring MQ destination and connection factories in a JMS foreign server.
The difficulty thing is how to authenticate the JMS client on Weblogic with the MQ server using a SSL certficate.

Originally I though I could configure my keystore on the "keystore" and "SSL" tabs of a Weblogic service. But this option threw the following exception:

[EJB:011014]The Message-Driven EJB failed while creating a JMS Connection. The error was:

com.ibm.msg.client.jms.DetailedJMSException: JMSWMQ0018: Failed to connect to queue manager '' with connection mode 'Client' and host name 'NAUMIB1.jpmchase.net(1414)'. Check the queue manager is started and if running in client mode, check there is a listener running. Please see the linked exception for more information.

Nested exception: com.ibm.mq.MQException: JMSCMQ0001: WebSphere MQ call failed with compcode '2' ('MQCC_FAILED') reason '2397' ('MQRC_JSSE_ERROR').

Nested exception: com.ibm.mq.jmqi.JmqiException: CC=2;RC=2397;AMQ9204: Connection to host 'NAUMIB1.jpmchase.net(1414)' rejected. [1=com.ibm.mq.jmqi.JmqiException[CC=2;RC=2397;AMQ9771: SSL handshake failed. [1=javax.net.ssl.SSLHandshakeException[sun.security.validator.ValidatorException: PKIX path building failed: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target],3=NAUMIB1.jpmchase.net/169.69.169.122:1414 (NAUMIB1.jpmchase.net),4=SSLSocket.startHandshake,5=default]],3=NAUMIB1.jpmchase.net(1414),5=RemoteTCPConnection.protocolConnect]

Nested exception: com.ibm.mq.jmqi.JmqiException: CC=2;RC=2397;AMQ9771: SSL handshake failed. [1=javax.net.ssl.SSLHandshakeException[sun.security.validator.ValidatorException: PKIX path building failed: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target],3=NAUMIB1.jpmchase.net/169.69.169.122:1414 (NAUMIB1.jpmchase.net),4=SSLSocket.startHandshake,5=default]

Nested exception: javax.net.ssl.SSLHandshakeException: sun.security.validator.ValidatorException: PKIX path building failed: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target

Nested exception: sun.security.validator.ValidatorException: PKIX path building failed: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target

Nested exception: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target.

at com.ibm.msg.client.wmq.common.internal.Reason.reasonToException(Reason.java:608)

at com.ibm.msg.client.wmq.common.internal.Reason.createException(Reason.java:236)

at com.ibm.msg.client.wmq.internal.WMQConnection.(WMQConnection.java:440)

at com.ibm.msg.client.wmq.factories.WMQConnectionFactory.createV7ProviderConnection(WMQConnectionFactory.java:7062)

at com.ibm.msg.client.wmq.factories.WMQConnectionFactory.createProviderConnection(WMQConnectionFactory.java:6453)

at com.ibm.msg.client.jms.admin.JmsConnectionFactoryImpl.createConnection(JmsConnectionFactoryImpl.java:295)

at com.ibm.mq.jms.MQConnectionFactory.createCommonConnection(MQConnectionFactory.java:6230)

at com.ibm.mq.jms.MQQueueConnectionFactory.createQueueConnection(MQQueueConnectionFactory.java:115)

at weblogic.ejb.container.internal.JMSConnectionPoller.getConnection(JMSConnectionPoller.java:473)

at weblogic.ejb.container.internal.JMSConnectionPoller.createJMSConnection(JMSConnectionPoller.java:1962)

at weblogic.ejb.container.internal.JMSConnectionPoller.connect(JMSConnectionPoller.java:780)

at weblogic.ejb.container.internal.MDConnectionManager.startConnectionPolling(MDConnectionManager.java:241)

at weblogic.ejb.container.manager.MessageDrivenManager.start(MessageDrivenManager.java:584)

at weblogic.ejb.container.deployer.MessageDrivenBeanInfoImpl.mdManagerStart(MessageDrivenBeanInfoImpl.java:1174)

at weblogic.ejb.container.deployer.MessageDrivenBeanInfoImpl.deployMessageDrivenBeans(MessageDrivenBeanInfoImpl.java:1154)

at weblogic.ejb.container.deployer.EJBDeployer.deployMessageDrivenBeans(EJBDeployer.java:1675)

at weblogic.ejb.container.deployer.EJBDeployer.deployMessageDrivenBeansUsingModuleCL(EJBDeployer.java:1450)

at weblogic.ejb.container.deployer.MDBServiceImpl.startService(MDBServiceImpl.java:69)

at weblogic.server.ServiceActivator.start(ServiceActivator.java:98)

at weblogic.t3.srvr.SubsystemRequest.run(SubsystemRequest.java:64)

at weblogic.work.SelfTuningWorkManagerImpl$WorkAdapterImpl.run(SelfTuningWorkManagerImpl.java:516)

at weblogic.work.ExecuteThread.execute(ExecuteThread.java:201)

at weblogic.work.ExecuteThread.run(ExecuteThread.java:173)

Caused by: com.ibm.mq.MQException: JMSCMQ0001: WebSphere MQ call failed with compcode '2' ('MQCC_FAILED') reason '2397' ('MQRC_JSSE_ERROR').

at com.ibm.msg.client.wmq.common.internal.Reason.createException(Reason.java:223)

... 21 more

Caused by: com.ibm.mq.jmqi.JmqiException: CC=2;RC=2397;AMQ9204: Connection to host 'NAUMIB1.jpmchase.net(1414)' rejected. [1=com.ibm.mq.jmqi.JmqiException[CC=2;RC=2397;AMQ9771: SSL handshake failed. [1=javax.net.ssl.SSLHandshakeException[sun.security.validator.ValidatorException: PKIX path building failed: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target],3=NAUMIB1.jpmchase.net/169.69.169.122:1414 (NAUMIB1.jpmchase.net),4=SSLSocket.startHandshake,5=default]],3=NAUMIB1.jpmchase.net(1414),5=RemoteTCPConnection.protocolConnect]

at com.ibm.mq.jmqi.remote.internal.RemoteFAP.jmqiConnect(RemoteFAP.java:2010)

at com.ibm.mq.jmqi.remote.internal.RemoteFAP.jmqiConnect(RemoteFAP.java:1227)

at com.ibm.msg.client.wmq.internal.WMQConnection.(WMQConnection.java:355)

... 20 more

Caused by: com.ibm.mq.jmqi.JmqiException: CC=2;RC=2397;AMQ9771: SSL handshake failed. [1=javax.net.ssl.SSLHandshakeException[sun.security.validator.ValidatorException: PKIX path building failed: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target],3=NAUMIB1.jpmchase.net/169.69.169.122:1414 (NAUMIB1.jpmchase.net),4=SSLSocket.startHandshake,5=default]

at com.ibm.mq.jmqi.remote.internal.RemoteTCPConnection.protocolConnect(RemoteTCPConnection.java:1020)

at com.ibm.mq.jmqi.remote.internal.system.RemoteConnection.connect(RemoteConnection.java:1112)

at com.ibm.mq.jmqi.remote.internal.system.RemoteConnectionPool.getConnection(RemoteConnectionPool.java:350)

at com.ibm.mq.jmqi.remote.internal.RemoteFAP.jmqiConnect(RemoteFAP.java:1599)

... 22 more

Caused by: javax.net.ssl.SSLHandshakeException: sun.security.validator.ValidatorException: PKIX path building failed: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target

at com.sun.net.ssl.internal.ssl.Alerts.getSSLException(Alerts.java:174)

at com.sun.net.ssl.internal.ssl.SSLSocketImpl.fatal(SSLSocketImpl.java:1611)

at com.sun.net.ssl.internal.ssl.Handshaker.fatalSE(Handshaker.java:187)

at com.sun.net.ssl.internal.ssl.Handshaker.fatalSE(Handshaker.java:181)

at com.sun.net.ssl.internal.ssl.ClientHandshaker.serverCertificate(ClientHandshaker.java:1035)

at com.sun.net.ssl.internal.ssl.ClientHandshaker.processMessage(ClientHandshaker.java:124)

at com.sun.net.ssl.internal.ssl.Handshaker.processLoop(Handshaker.java:516)

at com.sun.net.ssl.internal.ssl.Handshaker.process_record(Handshaker.java:454)

at com.sun.net.ssl.internal.ssl.SSLSocketImpl.readRecord(SSLSocketImpl.java:884)

at com.sun.net.ssl.internal.ssl.SSLSocketImpl.performInitialHandshake(SSLSocketImpl.java:1112)

at com.sun.net.ssl.internal.ssl.SSLSocketImpl.startHandshake(SSLSocketImpl.java:1139)

at com.sun.net.ssl.internal.ssl.SSLSocketImpl.startHandshake(SSLSocketImpl.java:1123)

at com.ibm.mq.jmqi.remote.internal.RemoteTCPConnection$6.run(RemoteTCPConnection.java:1005)

at java.security.AccessController.doPrivileged(Native Method)

at com.ibm.mq.jmqi.remote.internal.RemoteTCPConnection.protocolConnect(RemoteTCPConnection.java:1000)

... 25 more

Caused by: sun.security.validator.ValidatorException: PKIX path building failed: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target

at sun.security.validator.PKIXValidator.doBuild(PKIXValidator.java:294)

at sun.security.validator.PKIXValidator.engineValidate(PKIXValidator.java:200)

at sun.security.validator.Validator.validate(Validator.java:218)

at com.sun.net.ssl.internal.ssl.X509TrustManagerImpl.validate(X509TrustManagerImpl.java:126)

at com.sun.net.ssl.internal.ssl.X509TrustManagerImpl.checkServerTrusted(X509TrustManagerImpl.java:209)

at com.sun.net.ssl.internal.ssl.X509TrustManagerImpl.checkServerTrusted(X509TrustManagerImpl.java:249)

at com.sun.net.ssl.internal.ssl.ClientHandshaker.serverCertificate(ClientHandshaker.java:1014)

... 35 more

Caused by: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target

at sun.security.provider.certpath.SunCertPathBuilder.engineBuild(SunCertPathBuilder.java:174)

at java.security.cert.CertPathBuilder.build(CertPathBuilder.java:238)

at sun.security.validator.PKIXValidator.doBuild(PKIXValidator.java:289)

... 41 more

The above exception is complaining about the CA's used in the MQ server certificate are not available in my keystore. But I am sure I have these CA's in the keystore.

The real problem is the keystore you configured on Weblogic server "keystore" tab is only recognizable when the Weblogic server DIRECTLY connects to an SSL server.

In my case, my JMS MDB on Weblogic connects to the MQ server through IBM MQ API. So Weblogic is not directly connecting to the MQ server. You can see ths from the IBM packages "com.ibm.msg.client" and "com.ibm.mq.jmqi" in the above exception.

Finally in order to connect successfully, you just need to define the following 4 properties on the Weblogic startup cmd line:-D javax.net.ssl.trustStore=
-D javax.net.ssl.trustStorePassword=
-D javax.net.ssl.keyStore=
-D javax.net.ssl.keyStorePassword=

Technical Evalutions for a Real Time Searching System Part 1 -- Overview

2012-12-25T22:24:00.001-05:00

I recently conducted a technical evaluations for a real time search system (RTSS hereafter). It primarily focuses on mature open source frameworks. Many technologies involved are quite new and very interesting.
I present my ideas in a 4-part series:

Part 1 -- Overview
Part 2 -- Solutions Based on SQL and NoSQL DB (H2 and MongoDB)
Part 3 -- Solutions Based on Index Search Engines (Lucene Solar and Sphinx);
Part 4 -- Solutions Based on XML DB (MarkLogic and Berkeley DB XML)

1 Main Business Requirements for RTSS

Supports auto-complete and spell checkers on customized list of names;
Supports advanced searching and browsing on many combinations of attributes;
Support ranking / relevance;
Supports different types of clients (Java/C/C#) by being service-oriented;
Supports huge user based by being reliable and scalable;

2 Architecture Layers

The RTSS can be divided into 3 logic layers. From front-end to back-end, they are as follows:

The UI layer that includes web applications hosted on Jetty/Tomcat/JBoss, and non-web applications such as Java Swing and c/C++;
The service or business layer that provides results to the UI layer for auto-complete and spell-checker and all kinds of search requests either in a language neutral format such as XML, Fast Infoset, JSON or such descriptive binary protocol as Google Protocol Buffers;
The DAO layer that provides the service layer with search results. Data stores (SQL, NoSQL, index search engines and XML DB) will also be discussed along with DAO.

The 3 layers may be hosted on different servers for flexibility and scalability. However, they are usually combined together if possible for better performance. Data stores are usually on a separate server. However, in-memory DB can be embedded into the service layer.
In the following discussion, the lines or words in bold blue are viable options for final selection.

GPGPU High Performance Computing using OpenCL -- A Uniform and Portable API across Multi-core CPU and Many-core GPGPU

2012-12-25T21:35:00.001-05:00

Although this post overlaps with this previous one, it shows helpful diagrams and its approach is more systematic. Here it is.

1 Multi-Core CPU and Many-Core GPGPU

CPUs began from single-threaded serial processing of general-purpose tasks such as arithmetic, logic and I/O operations. For many years since then, CPUs improved the performance of single-threaded applications simply by reducing their latencies based on Moore’s Law [1]. Each new CPU provided increased clock frequency, which enabled applications to run faster. Applications performance was improved by merely porting them to the new CPU even without code modification.

However, every increase in clock speed imposes more demands on power and cooling requirements, and also tends to increase the disparity between CPU and host memory access times. To counter this, CPUs design employed complex low-level Instruction-Level Parallelism (ILP) [2] such as instruction pipelining, out-of-order execution and speculative execution while still keeping the frequency in economically allowed ranges. But, efforts to further exploit ILP have stalled since the late-1990s due to the following reasons:

1. ILP proves inadequate to keep CPU from stalling for host memory accesses because ILP often involves sophisticated hardware design and many applications have difficult-to-predict code;

2. Many applications need to process independent large data sets;

3. Many applications need to handle multiple concurrent tasks.

Instead, the industry shifted focus to applying Moore’s Law to implement more cores and larger caches per processor chip. Larger caches help to reduce the access time gap between CPU and host memory, especially for applications with spatial locality. Cores are units that execute a single stream of program instructions. A physical core, if it supports core-level multi-threading [3] such as Intel’s HyperThreading, is equivalent to two or more logic ones each of which supports one separate hardware thread (by hardware thread, we mean the execution context (program counters, registers, etc) is maintained on-chip during the entire lifetime of the thread so that context switching between threads can be done in just one cycle and virtually without cost. We will use “core” and “thread” hereafter unless otherwise noted). As you can easily reason, the more cores a system has, the greater parallel computing capacity. This is the case of GPGPU that can easily support tens of thousands threads.

However, these highly parallel computing processes do need us to parallelize application algorithms as much as possible in order to improve performance based on Amdahl’s Law [4]. Algorithm designers employ two commonly used Thread-Level Parallelism (TLP) models [5] to do so. One is Data Parallelism (DP) that decomposes data sets into multiple independent data elements to which a single stream of instructions are concurrently applied. DP is often used at fine-grained level and supported by a processor’s SIMD function [6]. The other is Task Parallelism (TP) that decomposes applications into many independent tasks that can be concurrently executed across different cores. TP is often used at coarse-grained level and supported by a processor’s MIMD function [6]. TLP improves overall application performance through high throughput of all threads, though latency is actually increased at individual thread levels.

Thanks to the commoditization of many of these parallel processors in the last decade, they are inexpensively available to us as either a workstation or a desktop cluster. Many large data set processing applications such as CT reconstruction, used to take many hours even several days on traditional serial CPU, can now finish in several minutes on these parallel processors without even resorting to any expensive proprietary hardware such as ASIC, FPGA, Cell BE or multi-node clusters.

Next, we will review two typical parallel processors: multi-core CPU and many-core GPU dedicated to General-Purpose Computing (GPGPU) and how OpenCL provides a uniform parallel computing paradigm for them. We conducted our researches on a Dell Precision T7500 Tower Workstation [7]. It features two Intel Xeon quad-core E5507 CPUs, and one Nvidia Tesla C2050 GPGPU. Because both processors represent relatively latest developments on parallel computing on CPU and GPGPU, our discussions are around them without loss of generality.

1.1 Multi-Core CPU

From the first 32-bit Intel Core architecture introduced in Jan 2006 up to the latest 64-bit Intel Xeon octo-core architecture [8], all multi-core CPUs share the same principle that it is easier to improve overall application performance using throughput-oriented multiple cores than using a latency-oriented single core. However CPU’s primary role as a general-purpose engine determines trade-off must be made among flow controls, caches and number of cores.

The 64-bit Xeon processors, as shown in Figure 1, represent Intel’s latest developments on multi-core and multi-processor. They target the server and workstation marets. Here are the highlights:

Each processor supports a maximum of 4 threads. HyperThreading is not supported;
Large on-chip L1,L2 and L3 caches (a total of 5.25M) and flow control (not shown in Figure 1);
Each processor supports 3 parallel memory channels that are totally 192-bit wide;
Each processor’s memory bandwidth is 19.2GB/s and peek single floating-point capability is about 36GFLOP/s;
Each core supports 128-bit SIMD vectors through SSE; MIMD is supported at processor level through the 4 cores;
NUMA supports – each processor accesses its locally attached host memory through the integrated memory controller much faster than access other remote host memory attached to the other processor through Quick Path Interconnect (QPI).

1.2 Many-Core GPGPU

From the first GPU invented in 1999 by Nvidia to process graphics only up to its latest Fermi-based Tesla products dedicated to general purpose computing [9] [10], GPU has evolved into a massively parallel processor that can run tens of thousands of threads on its hundreds of cores.

C2050, as shown in Figure 2, turns PCs and workstations into affordable small clusters. Here are the highlights:

Each Streaming Multiprocessor (SM) schedules parallel threads in groups of 32 called warps (AMD’s FireStream GPGPU, C2050’s equivalent, uses wavefronts for the same purpose. So we will use warps hereafter without loss of generosity) to 32 scalar cores. In other words, each SM maintains its own single stream of instructions of the kernel and each instruction is scheduled to 32 cores on different data in lockstep. This is how Nvidia implements SIMD using its so-called SIMT [11]. SM’s SIMD is 1024-bit wide that is much wider than E5507’s. MIMD is supported by scheduling concurrent kernels across the 14 SMs;
The 14 SMs support a maximum of 21,504 (1,536 x 14) active (resident) threads on the 448 (32 x 14) scalar cores thanks to the large amounts of registers. These numbers of threads and cores are much larger than CPU’s;
Small on-chip caches (the total is about 1MB) and simple flow control (not shown in Figure 2), which means higher latency than CPU;
Each SM support 48KB shared memory whose access time is between that of cache and global memory. This shared memory is explicitly available to programmers through API (on the other hand, caches are transparent to programmers). CPU doesn’t have such memory;
All SMs access the off-chip global memory through a wide 384-bit interface that has 6 parallel channels;
The device connects to the host through a PCIe x 16 Gen 2 slot. Its bandwidth is 8GB/s that is much slower than its 144GB/s memory bandwidth. The device’s peek single floating-point capability is about 1TFLOP/s that is much larger than E5507’s.

1.3 Different Workload Processing on CPU and GPGPU

Because today’s computer systems often form heterogeneous parallel computing ecosystems with CPUs, GPGPUs and / or other types of processors as shown in Figure 3 (T7500 ecosystem hereafter), it is important to know the type of workloads that each processor does best so that you can partition workloads and schedule them to appropriate processors using OpenCL. By doing so, you can access all the computing power (serial and parallel) of your systems, achieving very high system utilization.

GPGPU is suited to process large date sets while CPU is better suited to low parallelism (also serial operations such as disk and network IOs, and hard-to-parallelized programs).
This is because small data sets can’t justify the time incurred by GPGPU’s slow data transfer on PCIe and other setups. Large data sets also spawn a large number of threads that are required in order to take full advantage of GPGPU’s massively parallel structure and to hide its high latency on memory accesses and other operations;
GPGPU is suited to algorithms with high arithmetic density (the number of arithmetic operations per memory access).
This is also to hide GPGPU’s high latency. When a warp is stalled due to latency, SM swaps in a ready warp for execution, if any, through its fast context switch to maximize GPGPU utilization. Latency can be fully hidden if SM always has some arithmetic instructions to issue for some warp at every clock cycle during that latency period. Obviously the more arithmetic instructions and threads, the more latency is hidden;
Data transfer on PCIe should be minimized due to PCIe’s slowness.
In order to keep a high number of operations performed on GPGPU per data element transferred, you sometimes have to move more parts of your program to GPGPU even those parts perform faster on CPU;
GPGPU is suited to programs whose memory accesses have spatial locality.
Because off-chip memory accesses have the highest latency, both CPU and GPGPU access a block of consecutive memory such as 32 bytes instead of just the requested single data such as a 4-byte integer. However, GPGPU further coalesces memory accesses by a warp into as few memory transactions as possible. Better spatial locality means fewer memory transactions, higher cache hit rates and less waste of bandwidth. This is more important to GPGPU than to CPU because GPGPU has smaller caches and more threads;
GPGPU is suited to programs whose control flow logic is simple.
This is because SM schedules a common instruction to a warp at a time. Full efficiency is realized when all 32 threads of a warp agree on their execution path. If threads of a warp diverge via a data-dependent conditional branch, the warp serially executes each branch path taken, disabling threads that are not on that path, and when all paths complete, the threads converge back to the same execution path. So divergence leaves SM underutilized. This is also because CPU has more complex control flow logic and ILP mechanisms.

2 OpenCL – A Better Parallel Computing Paradigm

Parallel computing does need users to parallelize their algorithms using DP and / or TP of some programming paradigm. However, parallel computing for heterogeneous processors is challenging as traditional programming paradigms for CPU and GPU are very different.

For example, there are Pthreads and OpenMP for CPU, and they all assume a single shared address space and require users to possess complex multi-threading skills. GPGPU programming originally required users to possess intimate knowledge of graphics APIs (OpenGL or DirectX) and GPU architecture and to make their non-graphics applications look like graphics ones by mapping them into problems that drew triangles and polygons. This placed a great constraint for non-graphics domain users. This old approach was adopted by Fang et al in their CT reconstruction algorithm [12].

With the advent of Unified Shaders, GPU dedicated to general purpose computing (GPGPU) such as the Tesla series from Nvidia and the FireStream series from AMD, and programming paradigms such as CUDA from Nvidia and APP from AMD, CPU-based non-graphics applications can now directly access the tremendous performance of GPGPU without the above limitations.

Unfortunately all of the above different programming paradigms have very sharp learning curves (it should be very formidable for a non-computer domain expert to program all the parallel processors in the T7500 ecosystem using these paradigms) and some are vendor-specific. Worse yet, none of them may be supported by future parallel processors.

OpenCL [13] is an open industry standard for general purpose parallel programming across CPU, GPGPU, and other processors. From the software perspective, it is a framework consisting of an API to create host programs to coordinate parallel computing across heterogeneous processors, and a subset of ISO C99 with parallelism extensions to create kernels. OpenCL supports both DP and TP without users even knowing complex multi-threading mechanism. This, along with its support of universal C language, can greatly shorten the learning curve of non-computer domain scientists and engineers.

From the hardware perspective, OpenCL enables users to design portable, efficient and high-performance applications through its low-level, close-to-metal abstractions over heterogeneous processors (Although many details of the underlying hardware are exposed, OpenCL can’t expose all details. Otherwise OpenCL’s portability and programmability will be restricted).

In the following sub sections, we introduce these abstractions by borrowing some figures from OpenCL 1.0 specification [13], and mapping OpenCL concepts to the hardware in the Dell T7500 workstation. Readers should be able to figure out the function of each OpenCL concept based on the mapping and our previous introduction on CPU and GPGPU.

2.1 Platform Abstraction

Table 1 shows how the various components in Figure 4 map to CPU and GPGPU.

	E5507 CPU	C2050 GPGPU
Compute Device	the CPU chip	the GPGPU chip
Compute Unit (CU)	the 8 cores	the 14 SMs
Processing Element (PE)	the 8 cores	the 32 cores in each SM
Host	Dell T7500 workstation	Dell T7500 workstation

Table 1: Platform Mapping

OpenCL provides API to query all CUs connected to the host and to submit parallel computations on PEs.

2.2 Execution Abstraction

An OpenCL program consists of two parts: kernels that execute on one or more devices and a host program that executes on the host. OpenCL defines an index space called NDRange (the grid on CUDA) on devices. An NDRange can have 1 to 3 dimensions. Each point in the index space is called a work-item. When the host program submits a kernel to a device, an instance of the kernel (a thread) executes for each work-item.

Work-items are organized into work-groups at coarse-grained level, each of which is scheduled to one CU independently. Because C2050’s smallest execution unit is a warp, the work-group size should be a multiple of 32 for best performance. At fine-grained level, each work-term in a work-group can synchronize with each other on shared data accesses. Work-groups often work with local memory (defined in the next section) on GPGPU to eliminate redundant and stride access on global memory if your program possesses either of them and has spatial locality.

DP is supported by mapping each work-item to one or more data element(s). In strict DP, the mapping is one-to-one. OpenCL implements a relax version of DP where a strict one-to-one mapping is not required. You should determine the dimension size and mapping based on your program logic and the device’s capability. TP is supported by submitting multiple task kernels across CUs. Each of these kernels equivalently has only one work- item, which is wasting 31 cores on each SM of C2050. So TP is usually used on CPU each core of which executes one task kernel.

This execution abstraction is scalable because DP work-groups and TP task kernels can automatically and independently be scheduled to any available CU as the host scales to more CUs.

2.3 Memory Abstraction

Because C2050 caches global memory accesses into its L1 and L2 cache, the performance of applications whose memory accesses are not predicable (or possess poor spatial locality) can still be improved.

Because the on-chip local memory’s access time on GPGPU is close to caches, it should be used if a work-group’s spatial locality can be accommodated in it and the work-group items have redundant and /or stride access on global memory.

Both CPU and GPGPU have registers that consume zero extra clock cycles per instruction. OpenCL doesn’t explicitly expose registers. Instead kernel compilers usually optimize automatic variables to use registers. However if there are more automatic variable than available, these extra automatic variables will be place in the off-chip private memory and this is known as register spilling. The register usage usually has a significant impact on performance.

Since the constant cache on GPGPU is separate from the private and global caches in L1 and L2, it is not tainted by them. So it can improve performance if you can put constant data there, especially when your kernel doesn’t have good spatial locality.

	E5507 CPU	C2050 GPGPU
Global Memory	The off-chip host memory	The off-chip global memory
Local Memory	implemented in host memory	The on-chip shared memory
Private Memory	implemented in host memory	The off-chip local memory
Constant Memory	implemented in host memory	implemented in global memory
Global Memory Cache	implemented in L1, L2 and L3 caches	Implemented in L1 and L2 caches
Constant Memory Cache	implemented in L1, L2 and L3 caches	The constant cache

Table 2: Memory Mapping

My Recent Interview Experience in the Financial Industry -- Computer Science Fundamentals

2012-05-16T22:47:00.000-04:00

A base salary around $150k seems to be the watershed between a regular job that can be easily landed and a better paid job that needs a lot of efforts.
If you want to get better compensations, it is mandatory that you master computer science fundamentals. Most of financial firms I dealt with just didn't ask me any financial domain knowledge. Nor did they ask so-called populate technical skills such as Ajax, j2ee web development, Java Swing or JDBC etc. Instead, they just focused on fundamentals such as thread, socket, data structures and algorithms. Especially they wanted to make sure you are good at language-agnostic commonly-used data structures and algorithms.

I used to think that only hedge funds, prop trading firms, and high-profile technology firms such as Google and Amazon asked data structures and algorithms. But now it seems that other firms are just following suit.
For thread, it is not enough to only know how to create them. You also need to know thread safety, thread pooling, memory model etc.
For socket, it is not enough to only know TCP and UDP. You also need to know the Select paradigm and how to fine tune performance and latency.
For data structures, you should be very familiar with collection, set, list, queue, hash and tree.
For algorithms, you should know very well complexity analysis (the Big-O notation), all common sorting, median and order statistics, iterative and recursive, divide and conquer, exhaustive, back trace and dynamic programming.

There is a very well-known book "Introduction to Algorithms" from the MIT press. If you was not touch this book in school, you need to learn it by yourself unless you don't want to work for good companies.

If you have worked for many years, you feel it is not quite fare to be asked so many algorithms because new graduates usually have fresh memory on algorithms than you. But, if you think you are a smart guy who is willing to accept challenges, you should welcome any interview questions.

Speaking challenges, many firms also ask you some brain teaser questions. Basically the interviews wanted to test your analysis skills and logic reasoning capacities. Since most developers don't often face such problems at work, they feel it more difficult to work on them than on regular programming issues.
The good news is many brain teasers are relatively easier if you go through some training. A good source is the "Brain Teaser" link under my "INTERVIEW WEB SITES" section on the left.

Floating-Point Number Equality Comparison in Oracle, Sybase / SQL Server, Java and JMS

2011-11-02T11:26:00.001-04:00

As you know that computer can't store all floating-point numbers exactly primarily due to memory constraint. A double value such as 0.1 is actually represented as 0.1000000000000000055511151231257827021181583404541015625 in computer memory. Due to rounding errors, your equality comparison on floating-point numbers will probably fail.
In this topic I will show how SQL and Java store exact floating-point numbers (or just decimal numbers), and how floating-point literals are represented.

SQL99 uses FLOAT, REAL and DOUBLE PRECISION for approximate floating-point numbers, and NUMERIC(p,s) / DECIMAL (p,s) for exact floating-point numbers. For floating-point literals, SQL99 stores them as approximate floating-point types if they use the E notation (scientific notation); otherwise as the exact floating-point type if the literals meet the precision and scale of the exact types.
Because the NUMERIC(p,s) / DECIMAL (p,s) stores values without loss of precision for your decimal numbers, it should be used if you want to compare the equality between a floating-point column (in DB) or variable (in Java) to a decimal literal such as 0.1.
Different database vendors may have a bit different variants from the above specification.

Oracle 10g uses NUMBER(p,s) for both floating-point types in addition to its BINARY_FLOAT, BINARY_DOUBLE and FLOAT(p) for approximate types. Make sure you always specify the precision (p) for exact types.
If a floating-point is sufficed by f or F (for BINARY_FLOAT), or d or D (for BINARY_DOUBLE), it is of approximate types; otherwise of the exact NUMBER(p,s) type.

Sybase ESA 15 and MS SQl Server 2008 both comply with the above SQL99 standard very well. And both also have MONEY(SMALLMONEY) for exact float-point numbers.

Java has BigDecimal to store decimal values exactly. For example new BigDecimal("0.1") stores 0.1 exactly.

JMS's message selector is a string whose syntax is based on a subset of SQL92. Unfortunately JMS doesn't support exact floating-point numbers and restricts its exact numeric literal only to those without a decimal.

Key Concepts to Understand Spring's Consistent Transaction Handling

2011-08-17T22:52:00.002-04:00

Class FooBarService shows simplified pseudo code for different transaction handling paradigms using JDBC,Hibernate and JTA.

Class FooBarServiceSpring shows simplified pseudo code for consistent transaction handling using Spring.
Obviously Spring's transaction handling is quite different from JDBC and Hibernate; but is closer to JTA. However, by no mean does Spring only support JTA. Instead, it is only a matter of configuring different PlatformTransactionManager (PTM hereafter) in your application context in order to support different transaction handling paradigms.  For example, Spring's DataSourceTransactionManager, HibernateTransactionManager and JTATransactionManager are for JDBC, Hibernate and JTA, respectively.

This discussion can help readers understand some internals of Spring's  PTM implementations on heterogeneous native transaction platforms. 

//different transaction paradigms using JDBC,Hibernate and JTA

class FooBarService {    

  //local transaction paradigm using JDBC

  public void foo() {

    //creates a session with the backend database

    Connection conn = dataSource.getConnection();

    //starts a new local transaction.

    conn.setAutoCommit(false);

    updates-data-through-this-conn

    //commits the local transaction

    conn.commit();

    //closes the session

    conn.close();

}

  //local transaction paradigm using Hibernate

  public void bar() {        

    //creates a session with the backend database

    Session session = sessionFactory.openSession();

    //starts a new local transaction.

    Transaction tx = session.beginTransaction();

    updates-data-through-this-session

    //commits the local transaction

    tx.commit();

    //closes the session

    session.close();

}

  //Global transaction paradigm using JTA

  public void fooBar() {

    userTransaction.begin();

    //creates a session with the backend database1

    Connection conn1 = dataSource1.getConnection();

    updates-data-through-this-conn1

    //creates another session with the backend database2

    Connection conn2 = dataSource2.getConnection();

    updates-data-through-this-conn1

    //closes the two sessions

    conn1.close();

    conn2.close();

    userTransaction.commit();

}

}

//consistent transaction handling paradigms using Spring

class FooBarServiceSpring {

  @Transactional

  public void foo() {

    //updates data through some data source connection

}

  @Transactional(propagation=Propagation.REQUIRES_NEW)

  public void bar() {

    //updates data through some data source connection 

}

  @Transactional

  public void fooBar() {

    foo();

    bar();

}

}

1. Key Transaction Abstraction 
The following 3 interfaces are key to understand Spring's transaction handling: 
TransactionDefinition

It allows you to define transaction requirements (isolation level, propagation behavior, timeout and read-only status) before your transaction is started.

In FooBarServiceSpring, you specify your TransactionDefinition in @Transactional.
TransactionStatus

Once your transaction is started, this interface allows you to query its current status including rollback flag and new vs existing flag, and to mark it to rollback only (for example when you encounter an exception).

Spring's default TransactionStatus implementation also includes the underlying native transaction such as a connection for JDBC, a session for Hibernate and a user transaction for JTA.

In FooBarServiceSpring, @Transactional allows you to specify your rollback rules. For other status information, you either implicitly knows(such as IsNewTransactio and IsComplete) or can retrieve from the underlying native transaction bound to the thread (Spring binds JDBC connection and Hibernate Session to the thread; JTA's UserTransaction is also bound to a standard JNDI name).  Please note that Spring doesn't bind TransactionStatus to the thread because PTM can pass it around in your AOP proxied methods.
PlatformTransactionManager

It wires together the above 2 interface and works as a coordinate overall. 

Specifically its getTransaction() method takes your TransactionDefinition and creates a TransactionStatus representing either a new or existing transaction.  Its commit() and rollback() methods take the returned TransactionStatus and commit and rollback the target transaction, respectively. 

It allows you to demarcate transactions as a singleton because it can get different transactions bound on different threads.

In FooBarServiceSpring, @Transactional uses whatever transaction manager you configured in your application context such as DataSourceTransactionManager for JDBC.
When we say Spring transaction, we really mean TransactionDefinition and TransactionStatus. The PTM is more like a JTA UserTransaction / TransactionManager. But once again, it handles all types of native transaction API's behind the scene.
2. Physical Transaction and Logical Transaction
FooBarServiceSpring's foobar() calls foo() and bar(). Suppose there is no transaction before you call foobar(). So foobar() creates a new physical transaction while foo() starts a nested logical transaction due to its default propagation being REQUIRED; the logic transaction ends when foo() returns. 
But bar() suspends the current transaction and creates a new physical transaction due to its propagation being REQUIRED_NEW. The new transaction ends and the suspended transaction is resumed when bar() exits.
Because each (physical or logic) transaction always has a begin and end, we sometimes use transaction scope.

For data persistence, only the outer physical transaction can commit or rollback. But on each individual inner logic transaction (method) level, you always specify your TransactionStatus and can mark transaction to rollback . However the embed native transaction in TransactionStatus is either new (if it is a physical one) or existing (if it participates in an existing one).

You can also turn on the "validateExistingTransaction" flag in PTM so that the inner logic transaction will reject participation if its TransactionStatus is not compatible to the outer TransactionStatus.

3. Resource, Connection, Session, Transaction and Resource Manager (RM)
Resource can mean any valuable data; but in PlatformTransactionManager it is either a connection (for JDBC and JMS etc) or session (for Hibernate and JMS etc).

Both connection and session represent a communication link with the some backend resource manager (RM for short). In the database world, both termscan be used interchangeably. Although Hibernate uses session, it uses a connection behind the scene.

Transaction represents a unit of work. We mentioned in the above Section 1 that Spring's abstract transaction covers an underlying native transaction.
For JDBC and Hibernate, you create local transactions using connections / sessions and because they have one-to-one relationship, you can sometimes interchange the 2 terms. In other words, if the inner logic transaction participants in the outer physical transaction, it must reuse the the same connection / session.

For JTA, you creates global transactions using transaction managers; multiple connections can be enlisted in global transactions as transaction branches. One thing that is very different from JDBC and Hibernate is that you can conduct DML changes using different connections to the same backend RM instance in the same global transaction (This is because when a connection is enlisted, XID is created to represent this branch both in the JTA and the RM. Even you use a different connection, the RM can still identify the same transaction using the passed-in XID). 

RM managers resources (transaction) on behalf of you. It is commonly used in JTA/XA world. For most of us, databases are common RM.

4. Transaction and Session -- Which Comes First?
In the foo() and bar() of FooBarService, you first create a connection / session, then starts a transaction. Before you close the connection / session, you first commit / rollback the transaction.

But in the foobar() of FooBarService, you first starts a transaction, then create a connection / session. Before you commit / rollback the transaction, you first close the connection / session.

In FooBarServiceSpring, all you have is just @transactional and you are not allowed to open or close any connection / session explicitly. So how can Spring hide the difference between JDBC, Hibernate and JTA and whois taking care of connections / session anyway?

Data access experience tells us that we always need a connection / session and its lifecycle methods (open, close etc) are just boilerplate and resource will leak if you forget to call the close method (actually this happens very often). But we must define transaction requirements by ourselves. For example, only you know that the bar() in FooBarServiceSpring requires REQUIRE_NEW propagation based on your business rules.

So Spring is taking care of connections / sessions behind the scene. You just need to specify you transaction requirement using @transactional. The next section tell you more details. 

5. Transaction and Session -- Resource Synchronization with Transaction
Because you always explicitly specify your transaction requirements, Spring synchronizes the needed resource (connection or session) with the transaction at both transaction start time and ending time or at the transaction scope boundaries.

For JDBC and Hibernate, Spring binds the connection / session (hence also local transaction) to the thread so that it is always available on the execution call stack. 
Spring PTM automatically either retrieves an existing connection / session from the thread (if an outer transaction is already there) or creates a new connection / session and binds it to the thread before starting a transaction.
When transaction is right before being committed or rolled back, Spring PTM also automatically closes the connection / session and unbinds it from the thread.

 For JTA, Spring  gets the UserTransaction from the standard JNDI name, so the global  transaction is also available on the execution call stack.

When you retrieves a connection / session, it is automatically enlisted in the global transaction (Spring doesn't help here; the underlying XADataSource usually does the magic).
When the JTA transaction is right before being committed or rolled back, Spring PTM once again automatically closes the connection / session .

6. Nested Transaction and Transaction Suspend / Resume
For nested transaction, both  the outer and inner transaction are live in your thread while when a transaction is suspended, your thread work on another new transaction;
Nested transactions are dependent i.e. only the outer transaction is physical and can commit the change; but you can rollback the inner logic transaction.

The suspended transaction and the new transaction are two physical transactions and are independent i.e. they can both commit or rollback independently;
Suspending tranasction is deadlock-prone because the backend RM still holds the resource locks on the suspended transaction even your JTA has switched to another new transaction. You should be very careful even your application also locks some resources in the suspended transaction that are needed by the new transaction;
Nested transactions are only supported by JDBC with the savepoint feature. Because XA doesn't support nested transactions, neither JTA can (This seems to be ironic because most databases support savepoint);
Suspending a JDBC transaction in Spring means first unbinds it from the thread, then creates a new connection and binds to the thread. For JTA, Spring just delegates the suspend/resume to the underlying UserTransaction in addition to its own bookkeeping for resource synchronizations.
7. Propagation.SUPPORTS and No Transaction
No transaction means your data changes are committed on each individual SQL statement level (it is autocomit for JDBC) instead of grouping several SQL statements in a transaction.

Propagation.SUPPORTS also commits data changes on each individual SQL statement level if there is no existing transaction. But if you set your TransactionSynchronization in PTM to ALWAYS, it also supports resource synchronization on an empty transaction scope (empty transaction scope means no underlying native transaction).
To make it concrete, the same JDBC connection or Hibernate Session will bind to the thread inside the empty transaction scope for reuse in the execution call stack until the scope ends.  Be aware that the connection is of course in autocommit mode.

Please remember that if you empty transaction scope has active resource synchronization, DON'T nested Propagation.REQUIRED or Propagation.REQUIRED_NEW in it because resources synchronizations for the 2 transaction scopes will conflict (unfortunately you have to read the PMT source code in order  to get to the bottom).

Dynamically Creates Quartz Scheduler using Spring

2011-08-10T11:20:00.003-04:00

Here are my requirements: I need to dynamically create quartz cron triggers and add them to my scheduler. All my triggers schedule the same job but with trigger specific job mapping data.

Before I show how to dynamically create quartz schedulers using Spring, let's quickly review Sping's static configuration. The following excerpts come from "Chapter 23 Scheduling and Tread Pooling" in Spring 2.5.6 reference document and shows how to statically create a quartz scheduler:

<bean name="exampleJob" class="org.springframework.scheduling.quartz.JobDetailBean">
   <property name="jobClass" value="example.ExampleJob"/>
</bean>

<bean id="cronTrigger" class="org.springframework.scheduling.quartz.CronTriggerBean">
   <property name="jobDetail" ref="exampleJob" />
   
   <property name="cronExpression" value="0 0 6 * * ?" />
</bean>

<bean class="org.springframework.scheduling.quartz.SchedulerFactoryBean">
   <property name="triggers">
      <list>
         <ref bean="cronTrigger" />
      </list>
   </property>
</bean>

Spring's JobDetailBean extends quartz's JobDetail and provides the following added functions:

Setups sensible defaults in its life-cycle init method afterPropertiesSet() e.g. set the job's name to the bean name and set the job's group name to "DEFAULT" if they are empty (Remember that quartz scheduler uniquely identifies a job by its name and group);
Supports any job class that implements the Runnable interface besides quartz'a regular Job interface;
If your actual Job class extends Spring's QuartzJobBean, Spring also automatically injects the job map data to the job's properties;

Spring's CronTriggerBean extends quartz CronTrigger and provides the following added functions:

Setups sensible defaults in its life-cycle init method afterPropertiesSet() e.g. set the trigger's name to the bean name and set the trigger's group name to "DEFAULT" if they are empty (Remember that quartz scheduler uniquely identifies a trigger by its name and group).
Associates the trigger to the provided's JobDetail in afterPropertiesSet();
Set the trigger's timezone to the default one and start time to the current time afterPropertiesSet();
Sets trigger specific job map data through the Java's Map interface;

Spring's SchedulerFactorBean is a quartz Scheduler factory bean and wires jobs and triggers together. It implements many functions behind the scene that you have to do by yourself if you directly use quartz API:

Overrides default quartz properties e.g. thread pool parameters and jmx export;
Registers triggers;
Registers jobs. If you already assigned a job in your Spring trigger bean, you don't need this;
Sets the JobFactory to the default Spring's AdaptableJobFactory if it is not set by you. AdaptableJobFactory support Item 2 in the above JobDetailBean's added functions. AdaptableJobFactory's sublass SpringBeanJobFactory also supports the same function as mentioned in Item 3 in the above JobDetailBean's added function.
Schedules your jobs with quartz's scheduler;

All the above functions are implemented in the Spring' init method afterPropertiesSet().

Here are the steps to dynamically configure quartz scheduler using Spring to meet my above requirements.

Still configures my JobDetailBean, and my actual Job also extends Spring's QuartzJobBean in order to take advantage of the added function;
Still configures my CronTriggerBean using Spring in order to take advantage of the added function. But its scope should be "prototype" so that I can dynamically retrieve a new trigger bean instance and set its cronExpression and its job map data.
Here is the new trigger configuration:

<bean id="cronTrigger" class="org.springframework.scheduling.quartz.CronTriggerBean" scope="prototype">
<property name="jobDetail" ref="exampleJob"/>
</bean>

Here is the pseudo code:
CronTrigger ct = (CronTrigger)appCtx.getBean("cronTrigger");
ct.setName(ct.getName() + some-distinguisher);
ct.getJobDataMap().put(some-key, some-value);
ct.setCronExpression(some-exp);
Still configures my SchedulerFactorBean. But I need to add my above triggers to the scheduler. Because I create the above trigger after SchedulerFactorBean's afterPropertiesSet(), the trigger's associated JobDetail is not added to the scheduler. But I can explicitly register the JobDetail:

<bean id="scheduler" class="org.springframework.scheduling.quartz.SchedulerFactoryBean" lazy-init="false">
   <property name="jobDetails">
      <list>
        <ref bean="exampleJob"/>
      </list>
   </property>
   <property name="triggers"> 
      <list/>
   </property>
   <property name="autoStartup" value="true"/>
   <property name="quartzProperties">
      <props>
        <prop key="org.quartz.scheduler.jmx.export">true</prop>
        <prop key="org.quartz.threadPool.threadCount">2</prop>
      </props>
   </property>
</bean>
Here is the pseudo code:
Scheduler sched = (Scheduler)appCtx.getBean("scheduler");
sched.scheduleJob(ct);

Will class literals (some-named-type.class) cause class initialization?

2011-06-15T17:49:00.001-04:00

Suppose you have the following classes:

class Foo {
    static int cls_var = 10;
    static {
        System.out.println("cls_var:" + cls_var);
    }

    int inst_var = 20;
}

class Bar {
    public static void main(String arg[]) {
        System.out.println(Foo.class.getName());
    }
}

Will the class literal in bold blue cause Foo to be initialized (assign cls_var to 10 and run the following initializer)?
On the console you will only see "Foo"; you will not see "cls_var:10" as you may think you should see.

In order to find why, you need to know that JVM subject a class to the following 3 processes in order:

The class literal evaluates to the Class object for the named type (or for void) as defined by the defining class loader of the class of the current instance, and this information is accommodated by the above Step 1.

Foo's static variable initialization and the executor of static initializer are done in Step 3. Step 3 can be lazily executed by JVM after Step 1, which means Step 3 may not immediately follow Step 1.

This is why you will only see "Foo" output on the console. For more details, please see the linked JVM spec and Java language spec.

A GPGPU Article Published in DZone.com

2011-04-12T09:11:00.001-04:00

Large data set processing needs parallel computing that can be hosted on commodity processors ranging from low-end multi-core CPUs to high-end many-core GPUs. OpenCL can program both CPU and GPU, and even future parallel processors. Readers can learn from the article what workloads each processor is good at.

The article first discusses why OpenCL is a better programming paradigm for parallel computing on heterogeneous processors than others (OpenML,pThread, CUDA and ATI Stream); then compares the major hardware differences between CPU and GPU, and what different workloads CPU and GPU are each good at; finally a brief example is given regarding how to parallel an originally single-threaded algorithm to CPU and GPU using OpenCL.

This article was based on the coding experience with Lili Zhou, a medical physics resident at NY Presbyterian Hospital / Weill Cornel Medical Center. More discussions are expected as we are migrating more single-threaded programs to multi-core CPU and GPGPU.
This article is basically a rerun of my previous post.

Throws RunTimeException in Java Class Static Initializer?

2011-04-01T11:25:00.002-04:00

When you want to run some logic during class initialization, you put it into so called class initializer e.g. something like this:

public class MyTest {    

    static {

        if (some-condition)

           throw new RuntimeException("something wrong");

    }

    public void test() {

        System.out.println("throw RTE in static initializer");

    }

}

However there is some caveat. If the RuntimeException is thrown, class MyTest will still be loaded, but in erroneous state. So you can't do handle the following scenario.
Assume in the static initalizer, you want to retrieve some external property values and the RTE will be thrown if some property value is not configured yet. MyTest is also supposed to be deployed on the server side.
When JVM first attempted to load MyTest, the RTE was thrown because of some missing property value. The user saw the RTE and configured the missing property values. Now he/she hopes to be able to access this class.
However when MyTest is being accessed again, he/she will get NoClassDefFoundError.

This error is so confusing in this case because binary code of MyTest was indeed found by the JVM classloader. However it is just in erroneous state.
In order to find details, you need to read section 2.17 Execution in JVM Specification. Basically a class like MyTest must go throw 3 stages in order before it is being put in use: Loading, Linking and Initialization. The static initializer is executed in Initialization. If any exception is thrown in class initialization, JVM will throw ExceptionInInitializerError and put the class in erroneous state. (since the Initialization is after loading, the class was indeed found by JVM and loaded)
Based on Step 5 in section 2.17.5 in the above reference, JVM will stop initializing by throwing NoClassDefFoundError even the class has been found and loaded.

Because of this caveat, you have to throw an exception in a class constructor and use a class variable as a flag to void repeating execution of your logic that is supposed to be run only once.

A Data Replication Article Published in InfoQ.com

2011-03-01T18:58:00.001-05:00

Although data replication is an old technology as you can find it in Oracle Advanced Replicatin and Oracle RAC (Formally OPS), it is also widely used in some new products such as TimesTen, Gigaspaces and NoSQL.

This technical article is based on my previous posting "Locking Schemes for Data Replication Updating" and reviewed by Ron Bodkin, CEO of Think Big Analytics.

It discusses and compares several schemes commonly found in commercial and open-source products.
It helps you understand the prons and cons of different data replication scheme and assists you in choosing the right one suited for your business requirements.

Welcome to the World!

2011-02-28T16:49:00.001-05:00

My baby, Bryan Zhou Jiao, finally came to the world on Feb 15, 2011. Now I truly underdand how hard the ten-month long pregnancy is, which is especially true considering both my wife and me have passed the prime time for having a baby.
Fortunately the whole preganancy process basically went smoothly and both Mom and the baby are safe and healthy.
I am also a bit suprised so far. I am very afraid of baby crying and originally I though babies would cry very often. Luckily my little one is not worrisome and he only cried when he woke up and felt hungry, which seems to be his only requirement from us.

Here are some pictures.

More photos and videos are available at Flickr.

GPGPU High Performance Computing using OpenCL -- Parallel Computing on Heterogeneous Platforms

2011-02-26T23:36:00.002-05:00

The following technical discussion was co-authored with Lili Zhou who is a medical physics resident at NY Presbyterian Hospital / Weill Cornel Medical Center.
The discussion can help you understand the major hardware differences between multi-core CPUs and many-core GPUs (GPGPUs) and the different types of parallel workloads that CPUs and GPUs are each suited for.
Here it is.

Processing of large data sets entails parallel computing in order to achieve high throughput. Traditionally high throughput was only achievable through either proprietary hardware (Application-Specific Integrated Circuit (ASIC), Field-Programmable Gate Array (FPGA) or even Cell BE) or multi-node clusters.
However, as throughput-oriented multi-core processors become more pervasive, the same performance is now achievable through these commodity parallel architectures that range from multi-core CPU for low parallelism to many-core Graphics Processing Unit (GPU) for massive parallelism.

This article focuses on major hardware differences between CPU and GPU, which further decides the different workloads that each processor is suited for. In the end, it gives a data partition example using OpenCL across CPU and GPU, and compares the performance differences on the two platforms.

1 OpenCL – a New and Better Parallel Computing Paradigm

Because you most probably have different workloads that can be better processed using CPU than GPU or vice versa, you need to master parallel computing for both CPU and GPU.
However, parallel computing for heterogeneous processors is challenging as traditional programming paradigms for CPU and GPU are very different.

For example, you usually use POSIX Threads or Pthreads or OpenMP for CPU.
Although GPU typically only handles graphics computations, its gigaflops or even teraflops of floating point performance and high memory bandwidth make it suited to some non-graphics applications including data-intensive scientific and engineering computations, which actually falls into the scope of so-called General-Purpose Computing on Graphics Processing Unit (GPGPU).
However, GPGPU programming originally required programmers to possess intimate knowledge of graphics APIs (OpenGL or DirectX) and GPU architecture and to make their non-graphics applications look like graphics ones by mapping them into problems that drew triangles and polygons. This placed a great constraint for non-graphics domain scientists and engineers.
This old approach was adopted by Fang et al in the CT reconstruction algorithm.
With the advent of Unified Shaders, dedicated general purpose GPU such as the Telsa series from NVIDIA and the FireStream series from AMD, and high-level programming paradigms such as CUDA from NVIDIA and ATI Stream from AMD, CPU-based non-graphics applications can now directly access the tremendous performance of GPU without the above limitations.

Unfortunately all of the above different programming paradigms have very sharp learning curves and some are vendor-specific. Worse yet, none of them may be supported by future parallel processors.
OpenCL (Open Computing Language) is an open royalty-free standard for general purpose parallel programming across CPU, GPGPU, and such other processors as DSP and the Cell/B.E. processors, giving software developers portable and efficient access to the power of these heterogeneous processing platforms.
Although OpenCL is very new, it is a better choice because of the following factors:

It utilizes a subset of ISO C99 with extensions for parallelism. You are probably already familiar with C programming;
You don’t need to learn anything else in order to take advantage of the parallel structures of current and even future parallel processors;
You just need to analyze your algorithms for data or tasks decomposition without even knowing the underlying complex multi-threaded programming mechanism, not to mention any graphics API or GPU internals.

We will use OpenCL terminologies in the following discussion. If you are not familiar with them, you are encouraged to read the first three chapters in the OpenCL specification documentation.

2 Major Differences between CPU and GPGPU in Parallel Computing

You need to know the major hardware differences to be able to select either CPU or GPGPU for different workloads. This discussion uses Dell Precision T7500 Tower Workstation (it has 2 Intel E5507 quad-core processors without Hyper-threading) and NVIDIA Tesla C2050 for reference. You can click their hyperlinks to get introductions for their capabilities.
C2050 is based on NVIDIA’s next-generation CUDA architecture codenamed “Fermi” and has 14 CUDA 32-core multi-processors one of which is shown below courtesy of this resource:

2.1 GPGPU Supports Much More Hardware Threads than CP

T7500 only supports 8 hardware threads (4 compute units or core in CPU terms * 2 processors) while C2050 supports 21,504 (14 compute units or multi-processors in CUDA terms * 1536), which means C2050 is in a better position to process massive amounts of data in parallel than T7500.

2.2 GPGPU’s Threads Are Lightweight

By the above “hardware threads”, we mean the context or state of a processing element (one of the 4 compute units in T7500 or one of the 32 CUDA core in a C2050 compute unit) is saved in registers allocated to each thread so that context switching can be done in just one cycle.
If you create more than 8 threads for T7500, context switching will involve software operation, which takes many more cycles and are accordingly expensive and heavyweight.
Because C2050 has 32,768 registers, it can support as many as 21,504 in-flight hardware threads.

2.3 GPGPU’s SIMD and Global Memory Interface Is Much Wider than CPU’s

Single-Instruction Multiple-Data or SIMD is suited to process large data sets in batch mode. T7500 implements SIMD with SSE that is 128-bit wide while C2050 implements SIMD with Single-Instruction Multiple-Thread or SIMT (a smallest execution unit of 32 threads runs a single instruction) that is 1024-bit wide.
T7500 has 192-bit global memory (system memory in CPU terms) interface through 3 parallel channels per processor while C2050’s memory interface is 384-bit through 6 channels.
This means C2050 is better suited to large data sets that possess spatial locality.

2.4 CPU Has Larger Cache and Lower Latency than GPGPU

T7500 has 32K L1 and 256K L2 per compute unit and 4M unified L3 while C2050 has 16K L1 per compute unit and 768K unified L2, which means that CPU is more lenient to the requirement on spatial locality than GPGPU and also has lower memory access latency than GPGPU.
However GPGPU is optimized for high-throughput by hiding the latency for memory access and other instructions through fast context switching to ready threads in the scheduling queue, which assumes, in addition to there being a large number of in-flight thread, the number of arithmetic operations per memory operation is also high (Imagine if you only perform one arithmetic per memory load, context switching doesn’t make much sense).

2.5 GPGPU Gives Developers Direct control over Its Fast On-chip Local Memory

GPGPU’s local memory (shared memory in CUDA terms) approximately corresponds to CPU’s L1 cache with respect to latency.
This memory region is shared by all work items (parallel threads) in a work group (a thread block), and can be used to boost effective bandwidth and system scalability by reducing or eliminating redundant loads from global memory and coalescing stride accesses to global memory.
The coalescing of strides is possible only when memory accesses of all work items in a work group fall into the local memory. In other words, a work group exhibits spatial locality in the local memory.

C2050 has 48K local memory. Without using it, the redundant global memory loads from tens of thousands of threads if they do exist, will cause too many memory bus contentions, and un-coalesced stride accesses will waste too much memory bandwidth.

2.6 Data Needs Transfer Between GPGPU and Host

T7500 uses Gen2 PCIe X 16 for data transfer. Although the bandwidth of Gen2 PCIe X 16 is 8GBps, it is much lower than C2050’s memory bandwidth 144GBps.
So the number of compute operations per data element transferred in your parallel algorithms should be high otherwise they might be better handled using CPU.

3 Different Workload Processing for CPU and GPGPU

A fundamental requirement for parallel computing on both CPU and GPGPU is that you data or tasks can be decomposed for concurrent processing. However CPU and GPGPU are suited to different types of workloads.
On the other hand, if your data or tasks exhibit little or no parallelism, you should leave them to CPU for serial processing. OpenCL allows you to parallelize parts of your CPU-based applications by putting the parallel parts into an OpenCL kernel while leaving the rest untouched.

3.1 GPGPU Is Better Suited to Process Large Data Sets

Small data sets can’t justify the time incurred by GPGPU’s slow data transfer on PCIe and other setup costs. Large data sets also spawn a large number of lightweight threads that are required in order to take full advantage of GPGPU’s massively parallel structure and to hide GPGPU’s the latency for memory access and other instructions by fast context switching.

3.2 GPGPU Requires the Number of Arithmetic Operations per Memory Operation Be High

This is to hide GPGPU’s long latency for memory access and other instructions. Otherwise CPU is a better choice thanks to its larger cache.

3.3 Data Transfer on PCIe Should Be Minimized

In other words the number of compute operations by GPGPU per data element should be high otherwise CPU is a better choice due to the low PCIe bandwidth.

3.4 Memory Access Should Have Spatial Locality

This appears more important to GPGPU than CPU because CPU has larger cache and GPGPU’s wider SIMD and memory interface otherwise only means waste of bandwidth and limited scalability across its compute units.

Please note that you can relax this requirement a bit for GPGPU if your parallel algorithm meets the above 3.2 very well because a large number of arithmetic operations do hide memory access latency. Actually this relaxation is also a winning point because in order to use CPU’s SIMD feature, you must explicitly pack your data into vectors, which requires your data to have perfect spatial locality.

4 Partition Your Data for Data Parallelism

The key to OpenCL programming is to partition your data or tasks so that they can be processed in parallel. Task parallelism needs to vectorize your data and / or to submit multiple small kernels.
Since you face data parallelism most of the time and it needs more data design consideration, this discussion will only deal with data parallelism.
Data parallelism allows you to concurrently apply the same OpenCL kernel (the function to run on GPU in parallel) to multiple independent work items (data elements) in an OpenCL index space (a memory object decomposed into data elements). OpenCL doesn’t require you to have a one-to-one mapping between work items and data elements.

When you design a new parallel algorithm, you should put the requirements in Section 3 into consideration. A good candidate for parallelism is the FOR or WHILE loops with large iterations, and large data arrays.
One loop or one array can correspond to one dimension in an OpenCL index space while the loop iterations and array elements can map to work items. Nested loops or multi-dimension arrays can correspond to up to three dimensions in an OpenCL index space.

When you try to parallel an existing singled-threaded algorithm, you should also target its loops and data arrays and analyze its data access pattern to decide which processor is better suited, CPU or GPGPU?
If you are not sure about the selection, which is especially true when your existing algorithm doesn’t fit the requirements in Section 3 one way or the other (for example, the algorithm doesn’t possess too much spatial locality), you can first parallelize it to CPU. Then you can enhance it to GPGPU with slight modifications (still remember that OpenCL is a general purpose parallel programming paradigm across CPU, GPGPU and other processors?) and compare them.

This approach is what we did for our CT image reconstruction program – Conebeam.
The Conebeam runs on Dell Precision T7500 Tower Workstation equipped with a NVIDIA Tesla C2050. It has one one-dimensional input array, one one-dimensional output array, and three nested FOR loops that result in about 100M final iterations. The three FOR loops dynamically calculate the indexes for both arrays and compute the output array values based on the input array.
There are more than 200 arithmetic operations per memory access. Only the input and output arrays need transferring to and from GPGPU, respectively.

Here is pseudo-code method to parallelize on GPU:

01.void someMethod(float *inBuf, float *outBuf) {

02. for(int angle=0; angle

03. for (int binX=0; binX

04. for (int binY=0; binY

05. //the number of final iterations here is about 100M

06. int idxIn = calculate based on angle,binX and binY;

07. int idxOut = calculate based on angle,binX and binY;

08.

09. outBuf[idxOut] = calculate based on inBuf[idxIn];

10. }

11. }

12. }

13.}

Because the three FOR loops calculate the values of the output array independently, they can be parallelized as the three dimensions in an OpenCL index space.
Because the three FOR loops have large iterations, and the two arrays are also large, this program seems to be a good candidate for GPGPU.
However, because the index accessing order of the two arrays is not synchronous with the three FOR loop iteration order, this program has very bad spatial locality and local memory can’t be used. Fortunately because it has high arithmetic operations per memory access, it should hide memory access latency in some degree if we use GPGPU.

Before we compare the two OpenCL implementations with real tests, here is some estimation:
Since T7500 has 8 compute units running at 2.2GHz while C2050 has 16 compute units running at 1.1GHz, T7500 has an approximate equivalent of 14 C2050 compute units.
T7500 has 192-bit global memory interface through 3 parallel channels per processor, so its overall memory interface is 384-bit. C2050’s memory interface is also 384-bit through 6 channels.

The significant differences include (a) T7500 has just one processing element per compute unit while C2050 has 32 processing elements per compute unit; (b) T7500 has much larger cache than GPGPU and (c) T7500’s memory bandwidth is 230GBps while C2050 is 144GBps (GPU usually has higher bandwidth than CPU. However this high-end E5507’s effective memory speed is 4.8GHz while C2050 is only 3.0GHz).

The GPGPU version should be approximate 32 times faster than the CPU version if we put aside the cache factor and the CPU version doesn’t use SSE feature (The algorithm’s spatial locality is so bad that the above (c) shouldn’t generate any advantage to the CPU version).

Here are the real testing results:
The original single-threaded version ran about 70 minutes. The CPU version didn’t use SSE in order to port to NVIDIA GPGPU version easily and it ran about 12 minutes. The GPGPU version ran about 1 minute.
The CPU version didn’t have 8 times improvement over the single-threaded version because the Conebeam doesn’t have spatial locality and the 4 cores per processor incur memory bus contentions.
The GPGPU version didn’t have 32 times improvement over the CPU version because again the Conebeam doesn’t have spatial locality and CPU has much large cache.
In order to have linear scalability on GPGPU, the algorithm should be enhanced to exhibit spatial locality if it is possible.

5 Further Discussion

A major challenge for GPU programming is to preserve GPU performance levels while increasing the generality and expressiveness of application interfaces.
Although OpenCL, CUDA and ATI Stream relieve programmers from learning graphics jargons, they may not allow you to make good use of all GPU resources. The authors are not sure whether this concern still hold true even with NVIDIA’s Telsa series and AMD’s FireStream series.

While OpenCL provides programming portability, it doesn't necesssarily provide performance portability.

GPGPU High Performance Computing using OpenCL -- Work with Multiple Vendor Platforms using ICD

2011-02-02T11:49:00.001-05:00

Sometimes you have different workloads that are better handled with different vendor OpenCL implementations.
For example if your data presents access locality or coherence, the number of calculation per data element transferred on PCI is high and the number of calculation per memory access is also high, you can use NVIDIA's OpenCL implementation on its GPGPU.
On the other hand, if your data doesn't possess all of the characteristic mentioned above, you can use ATI/AMD's OpenCL implementation on CPU so that you at least can take advantage of all your CPU cores.

OpenCL has an extension "cl_khr_icd". It is technically called OpenCL ICD (Installable Client Driver) that is a means of allowing multiple OpenCL implementations to co-exist and applications to select between them at runtime.

In my case since I have both CPU and GPGPU-friendly data, I installed on a 64-bit Windows 7 workstation both NVIDIA GPU Computing SDK 3.2 that support OpenCL 1.0, and ATI Stream SDK 2.2 that support OpenCL 1.1.

1. Find out whether your Vendor's SDK Supports OpenCL ICD
You can compile and run NVIDIA's oclDeviceQuery program. If you see "cl_khr_icd" in section "CL_DEVICE_EXTENSIONS" it means NVIDIA supports Opencl ICD.
You can also run ATI's "clinfo" program. It actually prints out all OpenCL platforms. Again if you see "cl_khr_icd" in section "Extension" it means the corresponding platform supports Opencl ICD.

2. How does ICD Work?
Although I setup all my Visual Studio projects with NVIDIA GPU Computing SD, I basically can still dynamically load ATI's CPU OpenCL implementation.
The project setup basically needs two configurations. One is to specify the OpenCL include directory that contains vendor-neutral headers such as cl.h, cl_ext.h and some vendor-specific headers such as cl_agent_amd.h for AMD.
Unless your SDK's have different OpenCL versions, all vendor-neutral headers should be the same. If you need vendor-specific headers, of course you have to setup your project with that vendor's SDK.

The other configuration is to specify the OpenCL library directory where a vendor-neutral stub library "OpenCL.lib" is located. This "OpenCL.lib" is called ICD loader that is responsible to dynamically load a vendor specific ICD library.
When you install a OpenCL SDK, the SDK registers its ICD DLL in the register key
HKEY_LOCAL_MACHINE\SOFTWARE\Khronos\OpenCL\Vendors on Windows if it supports ICD.
So the ICD loader can scan the above register key and dynamically load your vendor's DLL library.

For more information, please refer to this resource.

3. How does ICD affect your Code?
Your application is now responsible for selecting which of the OpenCL platforms present on a system it wishes to use, instead of just requesting the system default.
This means using the clGetPlatformIDs() and clGetPlatformInfo() functions to examine the list of available OpenCL implementations and selecting the one that best suits your requirements.

For example, previously you could call the following function without specifying the specific platform value:
context = clCreateContextFromType(
     0, CL_DEVICE_TYPE_GPU, NULL, NULL, &status);

With ICD, you must specify a specific platform:

cl_context_properties cps[3] = {
              CL_CONTEXT_PLATFORM,
              (cl_context_properties)platform,
              0};
context = clCreateContextFromType(
     cps, CL_DEVICE_TYPE_GPU, NULL, NULL, &status);

GPGPU High Performance Computing using OpenCL -- Installation and Setup

2010-12-11T14:50:00.006-05:00

High Performance Computing (HPC) with General-Purpose GPU or GPGPU is one of the hottest technologies when it comes to massive amount of data processing.
Compared to the general-purpose CPU, GPGPU adapts some innovative new approaches to parallel computing both from software and hardware perspective.

When it comes to program GPGPU, OpenCL is the clear choice because it is the open standard for writing programs that execute across heterogeneous platforms consisting of CPUs, GPUs, and other existing or future processors. And almost all major GPU vendors including Nvidia and AMD(ATI) support it, which was manifested by their OpenCL 1.0 driver releases recently.

I have been studying GPGPU for several months. Now I get a real chance to help some scientists process some medical image data. Here are what I have.

64-bit Windows 7 professional;
Dell Precision T7500 Tower Workstation. It includes 2 Intel's latest 64-bit Xeon quad-core processors (a total of 8 physical cores. no HyperThreading), 6GB DDR3 ECC main memory, Broadcom NetXtreme 57xx Gigabit NIC, and ATI Firepro 3D V5800 for the display.
Nvidia Tesla C2050 GPGPU. It has 448 CUDA cores and 3G GDDR5 ECC global memory. It is Nvidia's flagship product to build a powerful workstation.

1. Install C2050
You can really build a personal supercomputer (or a mini-cluster) right on you desk using T7500 and C2050. Unfortunately T7500 and C2050 came separately and installing C2050 on T7500 is not that straightforward as what the C2050 installation instructions tell you inside its CD package.

With C2050 you can basically configure 2 ways:

Keep the existing ATI Firepro as the display adapter and the new C2050 as a pure computing co-processor (not use it to drive display).
Use C2050 as both the display adapter and a computing co-processor.

Configuration 1 is my case. I believe many people also want to have this configuration.

The first step in the C2050 installation instructions is to remove current graphics driver. This should only work for configuration 2.
My first attempt strictly followed the instructions. I downloaded and installed the latest Nvidia driver 263.06 and its GPU Computing SDK 3.2. My monitor was still connected to the FirePro adapter. The Windows Device Manager shows a standard VGA adapter and Tesla C2050 adapter both of which are working properly.
However when I ran the oclDeviceQuery OpenCL example in the SDK, C2050 was not recognized.
I am not sure whether it will work if I connect the monitor to C2050 and disable the standard VGA driver. I didn't put any more effort into it because I really want to have configuration 1.

So my next attempt was to restore the ATI Firepro driver. Unfortunately my previous uninstalling did some damage and I couldn't restore the ATI Firepro driver even the installation files still seem to be under c:\drivers\video\R259137\packages\drivers. So I downloaded the latest FirePro V5800 driver package on AMD's website and finally restored.
Now when I tried to run the same oclDeviceQuery, I got the same result. Actually even when you try to run any of the CUDA examples in the SDK, it didn't work neither.

In order to make C2050 recognized, you need to enable it to work in the so called TCC (Telsa Computing Cluster) mode instead of the WDDM mode. Basically the TCC mode enables the Tesla C2050 to work as a computing co-processor along with a display adapter among other functions.
Nvidia's release document for C2050 driver is so confusing at this point. The document mentions TCC is the default mode for C2050 that made me think it would be in TCC mode when I installed it. But it is not in my case.

I tried to run nvidia-smi to enable TCC mode but it complained there was no TCC GPU detected.
In order to enable TCC mode, you have to manually edit the Windows registry by adding a DWORD entry called "AdapterType" and setting its value to 2. This new entry should be under
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\ Class\{4D36E968-E325-11CE-BFC1-08002BE10318}\0001 (or 0000 or whatever number that corresponds to your C2050 adapter).
After the above change, you have to reboot. After reboot, when you can run the same oclDeviceQuer, you will see Telsa C2050 is successfully recognized.
Please be noted that because TCC mode disable the graphical functions, none of graphical examples will work.But isn't this what you want? The TCC mode is faster than the WDDM mode for computing and let the display adapter to do graphics.

2. OpenCL Support By Tesla C2050 Driver
Another confusing point in the C2050 driver release document is it didn't mention to support OpenCL. It only says to support CUDA C/C++. Fortunately the testing with its OpenCL examples show it indeed supports OpneCL 1.0 (actually if you examine the files installed by the 263.06 driver package, you can find the opencl.dll library).

3. Install OpenCL SDK
Nvidia's Developer Zone also seem to be confusing. When I just want to setup a computing SDK for GPGPU(not graphics), I was at loss what to download.
Basically you have to download 2 SDKs after you have installed the C2050 Driver (the driver package includes both the low level CUDA driver and OpenCL driver).

NVIDIA GPU Computing Toolkit. It includes both CUDA and OpenCL SDKs.
NVIDIA GPU Computing SDK 3.2. It includes SDSs for CUDA, OpenCL and DirectComput. It also include samples.

For OpenCL development, you only need to install 2.
On Windows 7, you probably have Visual Studio 2010. However the OpenCL example solution in the above 2 is for Visual Studio 2005 and 2008 only. The good news is Visual Studio 2010 can successfully convert the 2008 solution. The only major conversion warning is regarding the targetName is not consistent with the generated executable file name. But this will not cause you any trouble.

Commercial-Off-The-Shell Enterprise Real Time Computing (COTS ERTC) -- Part 4: Network Requirements

2010-11-21T21:46:00.002-05:00

Enterprise applications rarely work in isolation nowadays. Instead they usually cooperate with one another in a network environment.
Due to Ethernet's uniqueness, this topic will only discuss the TCP/IP suite over Ethernet. The networks in Figure 4.1 are used for the discussion.

Figure 4.1 Networks

1. Network Latency
The network latency from a host in LAN1 such as Host11 to a host in LAN2 such as Host21 is the cumulative latency of all the following component:

the TCP/IP stack latency on Host11. It includes all OSI layers except the 7th application layer (you have full control at the application layer). At least the 2 lower layers are implemented in the NIC firmware. All other layers are either included in the OS or also included in the NIC firmware.
the switch latency in LAN1. The switch is a Layer 2 device. Originally an unintelligent Layer 1 hub or repeater was used. I will compare the latency difference later on.
the routers latencies between LAN1 and LAN2. The routers are actually Layer 3 switches.
the switch latency in LAN2. Again the switch is a Layer 2 device.
the TCP/IP stack latency on Host21. Again it includes all OSI layers except the 7th application layer.
the propagation delay from Host11 to Host21. It is the time it takes for signals to travel in the physical copper cables or fibers. Signals in fibers or copper cables can travel at about 2/3 of the fundamental speed of light.
If the communication distance is short e.g. in a LAN, the propagation latency can be negligible compared to other larger latencies.
On the other hand if the the communication distance is long, it can't be ignored. For example the straight distance from San Francisco to New York is about 4,125 kilometers and the one-way signal travel needs about 19.6ms that is the lower bound of your overall latency optimization.

Network latency can also be defined as the round-trip latency between Host11 and Host12. However since our discussion focuses on latency and jitter analysis of all involving components, the above one-way definition is sufficient.

The data unit in our discussion is a packet. For example we can set it anywhere from the minimum Ethernet frame size (it is about 64 bytes) to the maximum MTU (it is about 1500 bytes) and compare the difference.
When you analyze your application level latency, the data unit is an application level request, which has complications when interacting with the underlying Maximum Segment Size (MSS) of TCP and the MTU of Ethernet frames (later sections will explain more details).

The prioritized latency and jitter analysis mentioned in Part 1 still applies here. For example upgrading to a faster switch in San Francisco doesn't make sense because the minimum latency to New York is bounded by the 19.6ms propagation delay and the latency of switches is usually in low micro-seconds.

The following sections will discuss the latency and jitter in all involving components.
2. Non-Determinism in Ethernet
Ethernet, as standardized by IEEE 802.3, is implemented at Layer 1 and 2 of the OSI model. Its latency comes from the processing delays at Layer 1 and 2. The latency has jitter because of its media access control (MAC) protocol - CSMA / CD at Layer 2.

With CSMA / CD, each host detects if another host is transmitting in the shared medium before it tries to transmit its own data (Carrier Sense). When a host detects a carrier, its Carrier Sense is turned on and it will defer transmission until determining the medium is free. This deference is unfortunately not predicable. If two hosts happen to transmit simultaneously (Multiple Access), a collision occurs and all frames are destroyed.

If we replace the switch in LAN1 / LAN2 with a hub / repeater, all four hosts will be in one collision domain. The more hosts trying to send data, the more collisions and the more non-deterministic.
Hosts sharing a half duplex connection are also in the same collision domain.For example even there are only Host11 and Host12 communicating to each other using a half duplex connection in LAN1, collisions still happen when Host11 and Host12 tries to send data to each other concurrently.

Although redesign of MAC protocol can solve the collision problem, it is not compatible to the existing ubiquitous Ethernet deployments and thus is appropriate and not a COTS solution.
If we can avoid collision, Ethernet will be much deterministic. This is what the switch in LAN1 / LAN2 is supposed to do. With the switch each host is guaranteed the exclusive use of the medium in both directions and is thus in a different collision domain from other hosts.
For example Host11 can communicate with Host12 while Host13 is communicating with Host14 without causing any collisions or frame drops.

3. Non-Determinism in TCP/IP
IP is at Layer 3; TCP and UDP are at Layer 4. The biggest jitter at these upper layers actually comes from the non-determinism of the underlying CSMA / CD.
For example if the underlying frame was dropped due to collision, the upper packet will be lost if it is UPD and will be retransmitted if it is TCP thanks to TCP's time-out mechanism.

A side note for TCP's time-out mechanism: if the network is slow, a low time-out value can lead to false retransmission. This is another reason why RTC applications prefer such fast networks as LAN.

You should also be aware of the following points
3.1 Non-Deterministic Routing Paths
A router has an additional Layer 3 compared to a switch. The more routers, the more potential communication paths between LAN1 and LAN2, and the more non-deterministic. A long communication path also leads to more frame drops due to data corruption. So a RTC system is usually enclosed in a LAN; otherwise make sure your routing path is deterministic.This is why many algorithmic trading systems especially high-frequency trading system, collocate with exchanges.

If the communication path is predicable, the determinism of a network with switches and routers will depend on that of those switches and routers. Modern switches and routers are actually very fast and can show very low jitter if managed properly, which will be discussed in Section 4.
.
3.2 Packet Header Overhead and Fragmentation
Each packet at IP, UDP and TCP layers has a header besides the real payload. The head size for IP, UDP and TCP is 20, 8 and 20, respectively.
Actually the Ethernet frame at Lay 2 also has a 20 bytes overhead. When an IP packet is greater than the Ethernet MTU (it is about 1500 bytes), IP needs to fragment and reassemble its packet.
TCP also fragments its stream into packets based on the MSS, the available window size and some other factors.

On one hand, more fragmentation and reassembly means more extra computing and higher latency. On the other hand, smaller packets than the MTU or MSS mean more significant header overhead and lower throughput.
In order to reduce jitter, your application level requests shouldn't have too variant sizes (different sized requests also mean different transmission delay). You should make your requests as large as possible before the latency misses your target. If possible, please decide the request size based on MTU.

3.3 TCP Flow Control
In order to avoid TCP packet drops from buffer overflows, TCP employs a sliding window mechanism to control its data flow.
So slow processing at the receiver host requires the sender host to send out smaller packets or even have to wait if the window size becomes 0. In order to reduce this jitter, make sure both ends can process network data fast and predictably.

If the network is slow, the sender may have to wait for the latest window size from the receiver. A fast network such as LAN can reduce this waiting latency.

3.4 Nagle's Algorithm
Because of the 20 bytes header overhead in TCP, Nagle's algorithm coalesces a number of small outgoing messages into one packet and sends it out.
This algorithm is usually unacceptable to RTC systems because they need immediate response for each of their requests. This is especially true when the RTC requests are small.

RTC systems usually take the following two counter-measures:

Enclose each request in one TCP packet;
Turn off this algorithm by using the TCP_NODELAY socket option.

3.5 Delayed Acknowledgment
Again because of 20 bytes header overhead in TCP, a pure TCP response packet will have too much overhead. So this mechanism delays the TCP layer response by waiting about one or two hundred milliseconds, and hopes to send back the response along with the upper application layer response using just one TCP packet instead of two.

Unfortunately a one or two hundred milliseconds deadlock can occur if this mechanism interacts with the Nagle's algorithm and your application's response doesn't synchronize with the TCP layer's e.g. an application request was sent out in two or more TCP packets. Please refer to this resource for a detailed analysis.

In order to avoid this jitter, you need to take one or more of the following measures:

disable the Nagle's algorithm;
disable or configure the delayed acknowledgment mechanism. Please refer to this resource on Windows; and TCP_QUICKACK on Linux;
Make sure your application level request is enclosed in one TCP packet.

3.6 UDP with Application Level Retransmission and Flow Controls
TCP implements its reliability at the cost of more computing work and header overhead than UDP. If TCP's reliability is more than what you want, you can use UDP and implement your simple reliability by yourself at the application layer. This approach should give your lower latency and jitter than using TCP.

4. Latency and Jitter of a Switch / Router
A router has an additional Layer 3 function. Its processing latency in a well-planed network will be predicable through a warm-up period that should cache all routing paths in the router. So we will focus on switches only.
A modern switch basically has two packet forwarding methods:

Store and forward. A whole frame is buffered before being forwarded. A checksum is usually performed on each frame.
Cut through. The switch reads only up to the frame's hardware address before starting to forward it. There is no error checking.

Because a cut-through switch doesn't have the additional buffering step, it has even shorter latency. However a cut-through switch will fall back to store and forward if its outgoing (egress) port is busy at the time a frame arrives. So we will focus on store-and-forward switches.

The one-way port-to-port latency of a switch is the cumulative delays of the following components:

Layer 1 processing at both ports including signal modulation and data framing;
Switch Fabric Latency. A switch has an internally shared high-bandwidth fabric that is much faster than any of its ports.
Store and forward latency;
Queuing latency. It occurs when different ingress ports are sending frames to the same egress port concurrently. Since only one frame can be transmitted at a time from the egress port, the other frames must be queued for sequential transmission in a FIFO manner. This phenomenon is called head-of-line blocking. Due to the FIFO behavior, the latency of a frame in the queue is unpredictable.
So each port of a switch has an outgoing queue, which along with the switch fabric actually gives the impression of simultaneous paths among its multiple ports.

Detailed analysis can be found from these two resources: Switched Ethernet Latency Analysis and Latency on a Switched Ethernet Network.

Both analyses show the queuing latency is usually the largest and a switch's jitter comes from it due to its unpredictable head-of-line blocking. .
In order to reduce the queuing latency and jitter, you need to take one or more of the following measures:

Plan your network traffic properly including a predicable many-to-one mapping from ingress ports to egress ports; a smaller many-side value if a higher predictability is needed; and more importantly, no egress port should be oversubscribed.
For example if you egress port is of 10GbE, you can only have a maximum of 10 1GbE ingress ports concurrently sending data to it; otherwise frame loss will occur. If you need some 1GbE port to have a higher predictability, you need to reduce the number of 1GbE ingress ports concurrently sending data to the 10 GbE egress port.
Because a switch's queuing jitter can cause avalanche effect at subsequent network hops, this is another reason why you need to reduce the number of routers in your networks;
Apply Virutal Lan (VLAN) or Priority values to different traffic. Make sure your RTC frames are in a separate VLAN or have the highest priority. This is similar to the different priority levels for RTC threads we discussed in Part 3.

Finally in this section, even a hub / repeater has lower latency than a switch thanks to its simple Layer 1 processing, a RTC system should not use it unless necessary such as port mirroring because it creates jitter.

5. Gigabit Ethernet
Ethernet evolved from 10BASE-T to 100BASE-T to the current widely deployed 1GbE or Gigabit Ethernet. Now even 10GbE has often been seen in backbone networks and high-end servers as a cheaper alternative to the appropriate and expensive high-speed interconnects such as Fiber Channel and InfinitBand.
A modern cut-through 10GbE switch such as BLADE'S RackSwitch G8124 can has an average port-to-port latency in 680 nanoseconds (the average is on latencies of several different packet sizes from the minimum 64 bytes to the maximum 1518 bytes).

Although this 680 nanoseconds latency is at the same magnitude as the main memory, the load on CPU increases linearly, without some kind of TCP offloading or OS kernel bypassing, as a function of packets processed, with the usual rule of thumb being that each bit per second of bandwidth consumes about a HZ of the CPU clock. For example 10Gbs of network traffic consumes about 10GHz of CPU that is much higher than the 3.33GHz of Intel's latest processor Core i7.
As more of the host CPU is consumed by the network load, both CPU utilization and host send / receive latency and jitter become significant issues.
RDMA over TCP/IP or iWARP has come up as a rescue. Basically an iWARP NIC or R-NIC allows a server to read/write data directly between its user memory space and the user memory space of another R-NIC-enabled host on the network without any involvement of the host operating systems.

API's have been implemented for different platforms including the OpenFabrics Enterprise Distribution (OFED) by the OpenFabrics Alliance for Linux operating system, and the Winsock Direct protocol for Microsoft Windows.

Commercial-Off-The-Shell Enterprise Real Time Computing (COTS ERTC) -- Part 5: Java Requirements

2010-11-09T17:37:00.002-05:00

Because programs designed using standard Java (either Java SE or Java EE or Java ME) exhibit non-deterministic timing of execution, standard Java is not widely used in RTC, especially in HRT.
However due to standard Java's popularity in many industries, extending it with RTC functions is very attractive. The Real-Time Specification for Java (RTSJ) is designed to seamlessly augment standard Java with RTC functions.

In this topic I will describe the key areas where standard Java creates jitters and how the two populate RTSJ implementations - Oracle's Java RTS and IBM's WebSphere RT - reduce them.
This is also a good time to compare RTSJ with C/C++ if they both run on the same underlying RT OS.

But before we start, here are few things about RTSJ:
Its implementations usually need a RT OS. Actually it is a must for HRT. In order to lower the learning curve, RTSJ doesn't introduce any new Java syntax, instead provides several new classes. Both Java RTS and WebSphere RT support Java SE 5 or later.

1. Threads, Synchronizations and Memory Management Models
Because Java threads have a one-to-one relationship with the underlying OS native threads (e.g. Java threads are implemented using the native POSIX threads on Solaris and stock Linux), most of Java threads' functions are delegated to OS native threads as we discussed in Part 3.

1.1 Regular Java Threads vs Java Real-Time Threads
Regular Java threads created by class java.lang.Thread (JLT) are not suitable for RTC due to the following factors:

JLT only has 10 priority levels, which is not enough for COTS ERTC.
JLT maps to OS non-real-time threads. For example, JLT maps to the SCHED_OTHER scheduling policy on Linux that creates jitter due to its dynamic priority adjustment.
JLT has the "priority inversion" problem because java.lang.Object.wait() doesn't implement the "priority inheritance" logic.
JLT doesn't provide priority-based synchronization because java.lang.Object.notify() is not required to wake up the highest-priority thread; and the "unlock" action in the "synchronized" statement is not required to choose the highest-priority thread to be the next lock owner.
JLT is subject to unpredictable pauses induced by GC because JLT allocates objects in the standard Java heap.

RTSJ provides a new thread type javax.realtime.RealtimeThread (RTT) to fix the above problems:

RTT must have at least 28 priority levels. For example Java RTS has a default of 60 on Solaris and 49 on stock Linux;
RTT maps to OS level real-time threads. RTT maps to the SCHED_FIFO scheduling policy on stock Linux which provides fixed-priority scheduling based on FIFO queues (another stock Linux RT scheduling policy "SCHED_RR" doesn't meet RTT requirements due to its round-robin feature).
RTSJ requires java.lang.Object.wait() implement the "priority inheritance" logic. On Linux RT and Solaris, it can delegate to the underlying POSIX threading services.
RTSJ requires java.lang.Object.notify() wake up the highest-priority thread, and the "unlock" action in the "synchronized" statement choose the highest-priority thread to be the next lock owner. On Linux RT and Solaris, they can again delegate to the underlying POSIX threading services.
RTSJ provides a subclass of RTT called javax.realtime.NoHeapRealtimeThread (NHRT) which is protected from GC-induced jitter (see next section for details). NHRT is intended for HRT.

Because RTT exposes many of the underlying OS native threading functions to Java, RTSJ can compete squarely with C/C++ in the above areas.

1.2 New Memory Management Models
Because NHRT is not affected by GC pauses, it is allowed neither to use the standard garbage-collected heap nor to manipulate references to the heap.
Besides the standard heap, RTSJ provides two memory management models that RTT and NHRT can use to allocate memory on a more predicable basis:

Immortal Memory.
It is not garbage-collected. Its primary use is to avoid dynamic allocation by statically allocating all the needed memory ahead of time.
It is like the malloc() / new operator in C/C++ without the corresponding free() / delete operator because once an object is allocated from it, the memory used by the object will never be reclaimed. Any unintended allocation into it is regarded as memory leak and can cause out of memory.
Scoped Memory. It is not garbage-collected either. It is intended for objects with a known lifetime such as temporary objects created during the processing of a task. It will be entirely reclaimed at the end of the lifetime such as when the task finishes.
Because many standard and third-party Java libraries create many temporary objects, it is impractical to use immortal memory if RTT or NHRT has to link to many libraries. In this case scoped memory is a better choice.

Although the two new models enable RTSJ to compete with C/C++ equally at the memory allocation area, they are hard to use and very error-prone because objects allocated in the two new models and the standard heap have difference GC characteristics and lifetimes, and assignment rules must be enforced.
So the recommended use of the two models is limited to programs that can't tolerate GC pauses such as in HRT.

1.3 Communication between NHRT and RTT / JLS
Because an NHRT could block on a lock held by an RTT or JLS. While the RTT or JLT holds the lock, GC could preempt it and indirectly preempt the NHRT. If this is not tolerable, you either should void lock sharing or use the following non-blocking queues for resource sharing:

javax.realtime.WaitFreeReadQueue class for passing objects from RTT / JLT to NHRT.
javax.realtime.WaitFreeWriteQueue class for passing objects from NHRT to RTT / JLS

Because many Java libraries use internal locking, NHRT linked to Java libraries must avoid indirect GC preemption to ensure HRT behavior.

Because the new JTSJ classes and RT functions above mentioned have a medium-level learning curve for Java SE developers, you are recommended to still use JLT with careful tunings if SRT can meet your business requirements. Those tunings included the OS level tunings as mentioned in Part 3, limiting the number of your application threads, avoiding of resource sharing and GC low-pause tuning as mentioned in Section 2 in this part.

2. Garbage Collection
Although automatic garbage collection provided by JVM greatly eases the memory management in Java compared to C/C++, it is unfortunately another big source of non-determinism.
Although standard JVM provides different GC algorithms such as serial, parallel and concurrent to allow users to make a trade-off between pause and throughput, all algorithms involve a stop-the-world (STW) pause, in which all application threads except NHRT are stopped so that GC can run without interference. This STW behavior is only acceptable for SRT or loose HRT.

Although RTSJ doesn't define deterministic GC, a RT JVM must provide one in order to support HRT. There are basically two approaches: work-based and time-based.
Both approaches are aimed to minimizing the effect of long pause by doing incremental collection in a GC cycle. Unfortunately neither can provide HRC guarantee.

2.1 Work-Based
Because the standard STW GC behavior blankly taxes all application threads, the work-based approach has each thread do a specific amount of incremental GC work proportional to its allocation amount each time it allocates an object.
However your application is still unpredictable because the GC cost spread-out is often uneven because the allocation is often uneven and the amount of time to do a fixed amount of incremental collection work is variable as shows in Figure 5.1 courtesy of this resource:

Figure 5.1 Risks of Work-Based Garbage Collection

2.2 Time-Based
It schedules a fixed amount of collection time in each GC cycle.
Although it spreads the GC cost equally through a GC cycle, there is no direct correlation between the allocated collection time and the reclaimed memory, and your application is still unpredictable as shown in Figure 5.2 courtesy of this resource:

Figure 5.2 Time-Based GC and Undesirable Outcomes

2.3 Oracle Java RTS 2's Approach
Java RTS uses a modified work-based approach called "Henriksson's GC" or Real-Time GC (RTGC). This RTGC can be configured to run as one or more RTTs that run at a priority lower than critical threads (NHRT and critical RTT) and higher than non-RT threads (JLS) and maybe non-critical threads as well (non-critical RTT) so that critical threads may preempt the RTGC, and RTGC may preempt non-RT threads and non-critical threads to keep up with the application memory allocation rate. This is shown in Figure 5.3 courtesy of this resource:

Figure 5.3 Henriksson's GC

The initial RTGC priority is lower than non-critical RTT but is boosted to its configurable "maximum priority" higher than non-critical RTT if remaining memory is close to another configurable "memory threshold". These two configurable parameters enable you to tune the balance between non-critical threads' deterministic and memory throughput.

Figure 5.3 shows that RTGC ensures HRT only for critical threads that should competes pretty well with C/C++, while trying to offer SRT for non-critical threads that usually can't compete with C/C++.

2.4 IBM WebSphere RT 2's Approach
WebSphere RT's Metronome is a time-based deterministic GC. It divides a GC cycle into a series of discrete quanta, approximately 0.5ms but no more than 1ms in length, that are devoted to either GC work or application work.
Even a single GC pause has an upper bound of 1ms, it is not enough because if several quanta were devoted to GC work, the application still experience a longer pause time as we discussed in Part 1. It must also meet another parameter called "utilization" that is the percentage of time quanta allocated to an application in a given window of time continuously sliding over the application's complete run.
Figure 5.4 shows a GC cycle divided into multiple 0.5ms time slices preserving the default 70% utilization over a 10ms windows courtesy of this resource:


Figure 5.4 Metronome GC Sliding window utilization

Compared to Oracle's RTGC, Metronome provides more determinism to JLT and non-critical RTT while RTGC ensures HRT for critical RTT. Because learning RTT takes time, Metronome is recommended to implement SRT with JLS.

2.5 Standard JVM's Approach

Both Oracle's Hotspot JVM and JRockit provide so called low-pause concurrent GC that only briefly pauses the application and runs concurrently with your application for most of the time.
Hotspot JVM allows you to specify both a target pause time and throughput while JRockit only allows you to specify a target pause time that seems to be inadequate based on our discussion in Part 1.
Such a low-pause concurrent GC can at best provide SRT.

Another very promising SRT implementation is provided by JRockit Real Time, which extends the existing mostly concurrent low-pause GC by ensuring the target pause time and limiting the total pause time within a prescribed windows (unfortunately such a windows can't be configured by users).
JRockit Real Time GC is more deterministic than the regular JRockit concurrent low-pause GC. Oracle claims it is the industry’s fastest JVM with its average response time in microseconds for most well-managed applications and low, single-digit, millisecond response with a five nines reliability guarantee. These numbers are pretty good for SRT even in the financial services industries.

Here is the biggest advantage of tuning GC compared to the new RTJS classes in Section 1: it is transparent to Java SE developers. In other words, it doesn't need developers to change their existing programming models or adapting to new RTC models.

Finally in this section it is often hard to pick a selection between SRT or loose HRT coded using C/C++ and SRT coded using Java along with a deterministic low-pause concurrent GC.

3. Class Loading, Linking, Initializing and Compilation
3.1 Class Loading, Linking, Initializing (LLI)
A standard JVM loads, links and initialize s classes on demand; it also unloads classes no longer referenced. Though LLI provides great flexibility on memory and CPU consumptions and the one-time cost can probably be made up if the same class is referenced multiple times, it is still another big source of non-determinism.
For example class loading usually takes at least tens of milliseconds because it usually involves disk IO. The linking and initializing are also very CPU-intensive.

You can eliminate the LLI jitter by pre-doing LLI in the application warm-up phase (it is defined in Part 3) either by calling the standard java.lang.Class.forName() or using RTSJ implementation-specific utilities.
For example, Oracle's Java RTS 2 allows you to either specify a list of classes for pre-loading and / or pre-initializing on the command line at JVM startup or use the Initialization-Time-Compilation (ITC) API during runtime (Both Java RTS and WebSphere RT can automatically generate a list of classes that were loaded or initialized by your application's execution).

Both approaches for eliminating LLI jitter are basically transparent to Java SE developers.

3.2 JIT vs Ahead-of-Time (AOT / ITC)
If you used C/C++ static compiler before, you know compiling (optimization included) is very CPU and memory intensive. So modern JVM JITs initially interpret Java methods and , for only those methods that execute frequently, later compile to native code.
Because the dynamic nature of Java makes much important information only available during runtime, JIT can generate even better code than statically compiled language like C/C++. Recompiling (deoptimization), overriding (virtual) method optimization and escape analysis are just three examples.
So if JIT can carefully balance the compiling time and optimization aggressiveness, the one-time compiling cost will be made up by the multiple later executions of the native code and the average execution time will be equal to or even shorter than the corresponding C/C++ program.

However because the compiling time is up to JVM and there is execution time variation between interpreted code and native code, the dynamic JIT is another big source of non-determinism.
The only solution to eliminate JIT jitter is to use some kind of static compiling such as AOT in WebSphere RT and ITC in Java RTS.

However AOT/ITC also has some disadvantages.
Firstly, the platform portability is comprised by AOT. ITC is a bit better due to its initialization-time compiling instead of AOT's development-time compiling.
Secondly AOT/ITC-compiled code, though faster than interpreted code, can be much slower than JIT-compiled or C/C++ code because AOT/ITC can only make few conservative optimizations with little information available at hand.

The debate of JIT vs AOT/ITC is still involving. Readers are recommenced to this resource to gain more insight. I personally recommend JIT because you can still achieve SRT and even loose HRT with it. With such fine tunings as warm-up and background JIT compiling, your Java programs can compete toe-to-toe with C/C++ programs.

4. Timers and Clocks
If RTC needs nanosecond resolution and your system can only provide milliseconds at beat, it will cause jitter.
RTSJ provides new classes javax.realtime.Clock and javax.realtime.HighResolutionTime to expose high-resolution clocks in underlying hardware and OS as discussed in Part 2 and 3.
You should also use the following standard Java methods if you need nanosecond resolution:
java.lang.Object.wait(long timeout, int nanos);
java.lang.Thread .sleep(long millis, int nanos);

You shouldn't use standard Java's java.util.Date or java.lang.System.currentTimeMillis() due to their low resolution and synchronization with the world clock (this synchronization looks like jitter when this world clock is updated).

In summary RTSJ can compete toe-to-toe with C/C++ in most areas for building COTS ERTC applications. The only concern is the learning curve of its functions extensions to standard Java. However the curve is not steep and often necessary for RTC.
If you had bias against using Java to build RTC systems, hopefully you will have a second thought after this discussion.

Locking Schemes for Replicated Data Updating

2010-11-05T15:47:00.003-04:00

Data distribution is commonly used in high-performance computing (HPC). Basically there are two fundamental data distribution topologies. One is replication; the other is partition.

With data partition, you can achieve parallel processing of a large amount of data.
With data replication, you can achieve load balancing and high availability(HA).

Even though a data item has several replicas in a data replication environment, it should have some degree of transparency and appear to only one virtual global item to end users.
The biggest challenge using data replication is the proper trade-off between data coherence and performance based on your business requirements.

Some kind of locking scheme is usually employed in order to achieve data coherence.
I will list some replication and locking schemes I have experienced using Oracle10g advanced replication, Oracle10g RAC, Oracle10g TimesTen and Gigaspaces XAP 7.1.

Before we go to details, let's suppose you have a distributed airline ticketing system (DATS hereafter) which has two databases: one is in NY and the other is in LA. Depending your replication scheme, data can be updated either at one site only and replicated to the other or at both sites and replicated to the each other.
Further suppose the following actions take place in time sequence:

There is only one ticket left in the database. Because both local database replicas are synchronized at this time, the only ticket can be taken by either NY or LA;
A NY customer bought this ticket. This action was updated in the local NY database and will be replicated to LA somehow depending on the replication scheme;
Depending on your replication scheme, the LA database can show the same ticket either still available or already taken by a NY customer. If the same ticket still appears available to the LA database, it will be sold to a LA customer. This will create an oversold situation.

1. Synchronous Replication Using Distributed Locks and Local Transactions

Oracle RAC (formerly OPS in version 8i and prior) allows the same physical database to be accessed at multiple instance sites. In order to allow users to read and write any data at any time at any instance site, Oracle RAC uses "Cache Fusion" to ensure data coherence.

"Cache Fusion" basically uses synchronous replication with a distributed locking manager (DLM). DLM acts as a distributed lock (DL) coordinator among other functions so that the same resource - e.g. a table row - can only be granted to one instance site for changing at a time while other sites have to wait.

DLM also act as a global resource directory. For example, when instance site 1 updated a row, it doesn't need to actively push the new version of data to all other instance sites. When instance site 2 later requests the same row, DLM can tell it to get the latest version from instance site 1.
Also instance site 1 doesn't need to use any distributed transaction thanks to DLM and the fact that there is still only one physical database (so far I haven't seen any synchronous replication that use both distributed locks and distributed transactions).

Benefits include very high degree of data coherence and load balance for both reads and writes.
Drawback include poor write performance and requirements of high-speed interconnect due to distributed locks.
Distributed locks usually consist of quite a few daemon processes and data structures at each site whose coordination performs poorly in a low-speed interconnect such as LAN and WAN. For Oracle "Cache Fusion", distributed locks are implemented with Global Cache Service (GCS), Global Enqueue Service (GES) and Global Resource Directory (GRD).

If we apply this scheme to DATS assuming the poor interconnect performance is tolerable, step 3 has to wait for the DL to be release by step 2. When step 3 gets the DL, the same ticket will show already taken by step 2.
(In order to have good performance, most multi-tiered applications use optimistic locking that can create lost update problem. For example if we use optimistic locking in both databases in DATS, the application tier in step3 can first read the LA database before step 2 and then sell the same ticket to a LA customer after step 2.
The application must use "optimistic locking with version checking" to fix this issue. One version checking is just a version number that increases whenever there is any corresponding data change.
Suppose the version is 0 at step 1. Step 2 updates it to 1. The version found by the application tier read at step 3 is also 0. But when the application tier tries to sell the same ticket, it will fail because it will find the version has changed to 1 from its cached value 0.
All our arguments assume "optimistic locking with version checking" .)

2. Synchronous Replication Using Local Locks and Distributed Transactions
Oracle's multimaster replication (also called peer-to-peer or n-way) has two data coherence protocols.
One of them is synchronous replication that applies any changes or executes any replicated procedures at all sites participating in the replication environment as part of a single distributed transaction. If the DML statement or procedure fails at any site, then the entire transaction rolls back.

The distributed transaction ensures data consistency at all sites in real-time. However it doesn't use any distributed locking. Instead it only uses local locks in the participant local transaction.
This is the case when an application performs a synchronous update to a replicated table. Oracle first locks the local row and then uses an after row trigger to lock the corresponding remote row. Oracle releases the locks when the transaction commits at each site.

Benefits include high degree of data coherence, simple implementation, easy administration and fit to both high-speed interconnect and low-speed LAN and WAN (implementing distributed locks in low-speed LAN and WAN is much harder than using lock locks in such environments).
Drawbacks include possible deadlock due to temporal behavior of local and remote locking, high availability requirements on network and poor write performance.

If we apply this scheme to DATS assuming the poor interconnect performance is tolerable, step 3 has to wait for step 2 to release the local and remote locks. When step 3 gets the locks, the same ticket will show already taken by step 2.

3. Synchronous Replication Using Local Locks and Local Transactions
TimesTen's unidirectional active-standby pair configuration only uses so called "return twosafe
replication". It provides fully synchronous replication between the master (the active site) and subscriber (the standby site).
No distributed transaction or distributed lock is involved. Instead only local transaction and local lock are used. Specifically the local transaction on the subscriber is first committed before on the master. If the subscriber can't commit, the master will not commit either.
At any time, only the active site can be updated that greatly simplifies data updating complexity (otherwise using local locks and local transactions will be insufficient) and ensures fast fail-over to the standby site in case of the active site failure.

This scheme has similar benefits and drawbacks to the previous scheme in section 2.
However its performance is even better thanks to the avoiding of two-phase commit (2PC) required in a distributed transaction. It also eliminates the deadlock because only the active site allows updates.
Although the standby site seems to be a waste of capacity, you can collocate it with another active site as shown in figure 1 (by another I mean it has different data from the collocated standby site).
This scheme has lower degree of data coherence due to the inconsistency resulted from master commit failure even the subscriber has successfully committed (the root cause is it doesn't use distributed transactions as you can guess. But you should also know that data inconsistency can still result from the second "commit" phase failure in a 2PC process).

TimesTen's practice in this scenario is consistent with its configurations for high performance in other areas such as asynchronous logging and data caching with write-behind policy,

Gigaspaces IMDG has a very similar topology called primary-backup replication. The only difference is it uses distributed transactions instead of local transactions only. So it has higher degree of data coherence than TimesTen.
Another advantage is the fail-over happens in Gigaspaces IMDG transparently to end users while TimesTen customers need to resort to some third-part cluster manager or some custom software.

If we apply this scheme to DATS, either NY or LA site will be the active site and the other standby site has to connect to the active for data updating (in reality, active-standby often is used with a high-speed interconnect). The local lock in the active site prevents the oversold situation.

This scheme along with data partitioning as shown in figure 1 is strongly recommend compared to the two previous synchronous schemes if it can your business requirements.
Although the two previous synchronous schemes allow updating anywhere, updating the same resource entails costly lock coordination over network. Scalable updating is usually achieved by data partitioning.
Although the two previous synchronous schemes allow distributed and scalable reads, you can fine-tune your partitions to allow more current reads.

Figure 1: The Primary-Backup Partition in Gigaspaces

4. Asynchronous Replication with Update Anywhere
Another data coherence protocol in Oracle's multimaster replication is asynchronous replication that allows users to update data at any participant site.
This scheme is also used in Oracle's updatable materialized view replication and TimesTen's bidirectional master-subscriber replication for general distributed workloads.

With this scheme the data changes at one site will be queued for propagation to other sites and committed locally. The queued changes will be propagated in batches in a separate transaction. So it doesn't use any distributed lock or distributed transaction. Instead it only use local locks required in the corresponding local transaction.

Benefits include great read and write performance, easy implementation, simple administration and fit to low-speed interconnection such as LAN and WAN and disconnected updating.
Drawbacks include limited degree of data coherence depending on data refresh frequency, and possible data change conflicts.
Because there is no distributed lock or distributed transaction involved, a replication conflict occurs if two transactions originating from different sites update the same row at nearly the same time (when the queued changes are propagated to the other site, the other site will have two versions of data changes. So which one should take place?).

A conflict resolution method must be provided to resolve the data inconsistency. Both Oracle and TimesTen have a prebuilt "latest timestamp" resolution method that makes the change with the latest timestamp the winner. Oracle also allows you to customize a resolution method based on your business requirements.

This scheme can't be applied to DATS if oversold situations are not allowed because the changes at NY and LA sites can be committed independently in two different transactions that result in the same ticket being sold to two customers.
If occasional oversold situations are allowed, the NY and LA sites can sell tickets at different times thanks to the three hours time zone difference. If a replication conflict does occur, relevant information should be recorded in the database based on which your front-end application takes proper actions (in reality a reservation system like DATS doesn't use this scheme).

5. Asynchronous Replication with Update on Master Site only

This scheme is used in Oracle's read-only materialized view replication, TimesTen's unidirectional master-subscriber replication and Gigaspaces IMDG's master-local replication.

This scheme basically has similar benefits and drawbacks to the previous scheme in section 4. However because it only allows updates at the master, it eliminates the notorious replication conflicts, which most of the time proves to be a very sound design in an asynchronous replication environment.

If we apply this scheme to DATS and suppose NY is the master site (or a third site is the master), NY has to wait if LA first gets the local lock at the master site. The local lock in the master site prevents the oversold situation.

Life is much easier using Gigaspaces IMDG's master-local topology as shown in figure 2 because it automatically delegates your local cache updating to the master which propagates the same updating to other local caches. Gigaspaces IMDG also supports optimistic locking with versioning.
You must do both by yourself if you use Oracle's read-only materialized view replication and TimesTen's unidirectional master-subscriber replication.

Figure 2: Gigaspaces Master-Local Topology where Master can be Figure 1

Duplicate Global Variable Definitions in C?

2010-11-03T00:08:00.007-04:00

If you are still a novel C developer, a common, however bad, practice of using a global variable is shown as follows:

/* global.h */
int globalInt;

/* file1.c */
#include "global.h"
void foo() {
globalInt = 1;
}

/* file2.c */
#include "global.h"
#include "stdio.h"

void bar() {
printf("the globalInt is %d", globalInt);
}

Neither Visual C++ studio 2008 nor GCC 4 has any complaint compiling and linking the program as C.

However you will get "duplicate definition" error if you try to link the same program as C++ either using VC++ or GCC.

After I made some researches and found the reason, I feel embarrassed because I have already been though C was just too easy.

In order to know the reason, you need to know the variable declaration, variable definition, and tentative definition and "multiple external definitions" in C99.

When you define a variable, you are telling the compiler to allocate memory for that variable, and possibly also to initialize its contents to some value.
For example int i = 100;

When you declare a variable, you are telling the compiler that the variable was defined elsewhere. You are just telling the compiler that a variable by that name and type exists, but the compiler should not allocate memory for it since it is done somewhere else.
For example extern int i;

Here are the two important rules you have probably already known:
A variable must be defined once in one of the modules of the program. If there is no definition or more than one, an error is produced, possibly in the linking stage.

A variable may be declared many times, as long as the declarations are consistent with each other and with the definition. It may be declared in many modules, including the module where it was defined, and even many times in the same module. But it is usually pointless to declare it more than once in a module.
Since the "globalInt" in our example is outside of any function, it has the "extern" linkage. so is the "int globalInt" a definition or declaration?
Based on C99, it is called "tentative definition" in Section 6.9.2 as stated below:

A declaration of an identifier for an object that has file scope without an initializer, and without a storage-class specifier or with the storage-class specifier static, constitutes a tentative definition.If a translation unit contains one or more tentative definitions for an identifier, and the translation unit contains no external definition for that identifier, then the behavior is exactly as if the translation unit contains a file scope declaration of that identifier, with the composite type as of the end of the translation unit, with an initializer equal to 0.
Based on the above C99 standard, both file1.c and file2.c should have the following definition after being compiled:
int globalInt = 0;

So if both VC++ and GCC strictly followed the C99 standard, the linking step should have failed due to duplicate variable definition.
However C99 does have an Annex J.5.11. as follows:

Multiple external definitions

There may be more than one external definition for the identifier of an object, with or without the explicit use of the keyword extern; if the definitions disagree, or more than one is initialized, the behavior is undefined (6.9.2).
So obviously both VC++ and GCC allow consistent multiple external definitions by extending the "tentative definition" to the entire program scope from the original file scope.

Now the last puzzle why C++ complained.
Because C++ treats C99 "tentative definition" as normal variable definition, you of course got the variable duplicate error.

How to effectively Manage Floating-Point Keys in C++ Map (or Set)?

2010-11-02T20:50:00.003-04:00

Because computers can't accurately store floating-point values as you know, you should try to avoid equality comparison between them or use some approach like "relative error" as mentioned in this resource.

I have a table of data where keys and mapped values are both floats. Although I can provide my own Compare logic using the above "relative error", this Compare template parameter is only used for "strict weak ordering". In other words, it only tells whether two floating keys in my case have a "less than" (<) ordering so that the Map can order keys in acceding order.

For example if Compare says the predicate of "float1 < float2" is false, it either means float1 = float2 or float1 > float2.
But the C++ Map doesn't allow you to customize either an equal or a greater than logic. This is especially troubling when you want to use Map's find() method based on floating-point values. In this case, the Map will use the computer's intrinsic equal(=) comparison logic, which is not reliable for floating-point value' comparison as you know.

Fortunately in my case I know the maximal precision and scale for all my floating keys. So I first safely mapped my floating key to integers and then saved the corresponding integer keys into the map.