CPU time vs. time

[NotThatItMatters]

I have a time simulation application running a fairly large model which requires a 64-bit executable to run.  Without the 64-bit executable, I get virtual memory errors.  Running the model in question, I am noting that, at this point, the model has been running 6 days and yet the CPU time is only 42,000 seconds.  With smaller models and runs, CPU time and real time are pretty much synchronized.  What sort of thrashing is going on which is causing this discrepancy?

[jimdempseyatthecove]

NotThatItMatters,

Sergey's post on Tue, 05/07/2013 - 17:32 is right on target. Use John Campbell's recomendation to see if excessive page faults are taking place. There is one additional thing to investigate relating to page faults. On Windows you can set the working page file at nnnn MB and have it variable (permit it to grow as necessary). Sounds good and benign. However, when an app requires the page file to grow, I have observed personally that this expand the page file process slows down the app to the point where you may think it has stopped (this appears to be what you are observing). The partial fix to this is to set your page file to a proper working size for your application.

I say "partial fix" because this will fix only the (potential) page file expansion issue. This will not fix excessive paging by a virtual application which is larger than physical RAM. The fix for "excessive paging by a virtual application which is larger than physical RAM" is to pay attention to data locality. IOW get as much work out of an area of data before moving onto different areas of data. i.e partition the work. Also keep in mind that if you come from C/C++ programming you program with the right most index of a multi-dimensioned array varying the quickest (as inner loop control variable). With FORTRAN, it is the other way around (use left most index as inner loop control variable).

Recommendations:

a) Set page file lower limit to at least working size for your application
b) Assure loop order with respect to Array(InnerMostLoopIndex, MiddleLoopIndex, OuterLoopIndex)
c) If necessary partition (sometimes called tile) work into smaller pieces which is done usually by adding an outer loop (or multiple outer loops). Example:

[fortran]

! process cells
do iRow=1,nRows
  do iCol=1,nCOls
...

Becomes

! specify tile size
iRowChunkSize = mmm ! you determine this value
iColChunkSize = nnn ! you determine this value
! now process tiles
do iRowChunk = 1,nRows,iRowChunkSize
  do iColChunk = 1,nCols,iColChunkSize
    do iRow=iRowChunk,MIN(iRowChunk+iRowChunkSize-1, nRows
      do iCol=iColChunk,MIN(iColChunk+iColChunkSize-1, nCOls)
        ! process cells in tile
        ...
[/fortran]

Jim Dempsey

[SergeyKostrov]

>>...c) If necessary partition (sometimes called tile) work into smaller pieces which is done usually by adding an outer loop >>(or multiple outer loops) I think Jim just described a Loop Blocking Optimization technique and it is highly efficient. >>a) Set page file lower limit to at least working size for your application... I'd like to provide two screen shots which demostrate how terrible the situation is when there is an excessive paging during processing: Here is a short description: - An older computer system has 1GB of Physical Memory ( PM ) and VM settings are: Initial Size = 256MB and Maximum Size = 2048MB - Application starts and allocates ~1.98GB of memory for a data set. So, ~0.90GB of memory from PM and ~1.08GB of memory from VM - A Red Circle shows an area with "VM Pillars" and during that time operating system is very busy with allocation of pages in VM file and performance of the application varies from ~5% to ~75% and an average number is ~30% ( it is very close to your 25%! ) - As soon as VM pages are allocated performance of processing increases ( you see a "Plateau" ) and CPU Usage is 100% ( everything is back to normal ) - In total 5 iterations of the same processing is done and during "VM Pillars" phase it takes ~300 seconds to complete all calculations and all the rest 4 iterations are done in ~75 seconds each ( almost 3x faster! / "VM Plateau" phase ) - "VM Pillars" phase could be classified as VM-Bound processing ( significantly reduced performance ) - "VM Plateau" phase could be classified as CPU-Bound processing ( performance is Not affected by VM operations )

[SergeyKostrov]

Here is a complete overview of processing: Three Circles show different phases of processing and let use know if you have any questions.

[Bernard]

This expected behaviour of the system "plagued" by heavy activity of page fault handler and memory manager allocation routines.I would like to see what is the percentage of time spent in kernel mode.I would like to add that Task manager is not the most suitable tool for performance measuring perfom is recommended on Win XP.I suppose that those spikes at the beginning can come from disk.sys DPC routines.

Sergey can you add perfmon disk I/O statistics?

[NotThatItMatters]

Thank you for all the insight.  In order to get the process running expeditiously, I will evidently need to figure out how to effectively partition the memory.  In general I have been using left to right indexing in multi-dimensional arrays.  There are several exceptions, specifically in the "solver" routine where the largest arrays are being handled.  Attached are three screen shots from the Task Manager showing execution.

Before going into the hows and whys, let me ask a novice question about stack size.  Suppose I have a routine as follows:[fortran]SUBROUTINE FOO(II, JJ, KK, A)

INTEGER, INTENT(IN) :: II, JJ, KK

REAL (KIND = 8), DIMENSION(II, JJ, KK), INTENT(INOUT) :: A

END SUBROUTINE FOO[/fortran]

What is the comparison in stack usage between this and the following?[fortran]SUBROUTINE FOO(II, JJ, KK, A)

INTEGER, INTENT(IN) :: II, JJ, KK

REAL (KIND = 8), DIMENSION(II, JJ, *), INTENT(INOUT) :: A

END SUBROUTINE FOO[/fortran]

[SergeyKostrov]

>>...Sergey can you add perfmon disk I/O statistics? No at the moment. You could easily simulate the same "terrible" situation with "VM Pillars" with a couple of Fortran or C/C++ code lines. So, please do your own research, coding, testing and analysis.

[Bernard]

Task manager screenshots confirm what has been alread said.I can add that reserved hardware MMIO is not high mainly because of low end on die gpu.Moreover page file is almost full which means extensive disk I/O and moving large portion of paged system memory to page file.Also superfetching will be affected because of very little amount of free memory not allocated to any process or device.

[NotThatItMatters]

Okay, now that it is resolved that page swapping is the likely cause of the slowdown, how can I fix this?

1) Will limiting stack size have an appreciable effect?  (See the previous post!)

2) Will array indexing have an appreciable effect?

This is a large executable with many routines.  I need to have some idea on how to solve this problem before I branch and test.

[John_Campbell]

NotThatItatters,

Two answers to some of your points,

1) There is not much difference between REAL (KIND = 8), DIMENSION(II, JJ, KK), INTENT(INOUT) :: A  and REAL (KIND = 8), DIMENSION(II, JJ, *), INTENT(INOUT) :: A .  The important thing is you should be trying to vary the II index in the inner loop and not the KK index. This will keep the memory being addressed local, as varying KK can span many mb or even gb, which drives the paging demand and kills cache benefits. This can be a significant issue for performance, even when there is no paging, as when you jump around memory, you loose the benefit of the processor cache. If this is a problem, changing the order of the array subscripts can help, but you MUST make sure you do this change for every use of the array.

2) If paging is the problem, you still have not indicated what is the memory size of the program. You need to have some idea of this size, to a) make sure your virtual paging size is big enough, and b) consider how much physical memory to install. The best solution to paging is to install more memory chips to reduce the amount of paging required. Another useful solution when paging occurs is to have a SSD disk for pagefile.sys, as this reduces disk io delays.

To answer your last post,
Not sure of your reference to stack size, but I don't think this is relevant. ALLOCATE is best for big arrays which do not use the stack.
Size of the executable is also not an issue, as the code size of many routines typically take much much less memory that the declared arrays. (initialising large arrays with data statements etc can have an influence on .exe size, but should not affect run time. I initialise arrays during run time, rather than at startup)
Array indexing/subscript order is a big, possibly huge factor.

You need to understand how much memory you are using in your simulation and understand the efficiency of memory addressing. Hope this helps.

John

[SergeyKostrov]

John provided you with tips for questions 1 and 2 and I'd like to repeat the same: It would be nice to install more Physical Memory, for example, 4GB or 8GB. Note: That was told already several times as far as I remember.

[John_Campbell]

Attached is a simple example of changing subscript order and loop order to change the run time. When mixing arrays of different sizes and different index orders, the result is not always clear. If you select li=lj and lk = 5*big, the variable performance changes a bit.
the attached example induces paging on my PC, to cause the time variations.

Edit: I updated the test to better show the effect of paging and hopefully memory cacheing for the different test sizes. You can experiment with values of li, lj and lk to get different effects, but from my tests, the best solution is not the same as memory footprint increases. My paging test was witha SSD disk, so it would probably be slower on a HDD. I have not tested /Qparallel !!

John 

[SergeyKostrov]

{ Correction } There are two statements: >>...Another useful solution when paging occurs is to have a SSD disk for pagefile.sys, as this reduces disk io delays... and >>...My paging test was witha SSD disk, so it would probably be slower on a HDD... So, you've simply confirmed that idea to use SSD is good.

[Bernard]

As Sergey suggested you can add more memory.Regarding SSD it has fater access time and reduced latency and it is advised to put pagefile.sys on SSD drive.But for prolonged time you will have some performance degradation if pagefile is used heavly.

[John_Campbell]

Sergey and ilyapolak,

Yes, you have identified that using an SSD and more memory both contribute to reducing the paging delays. Array dimensions and subscript indexing also contribute significantly to the number of page faults resulting in the calculation.

I have also tried to identify that by localising the memory addressing in the computation that the cache usage can be improved significantly, further inproving the run time performance. The contrary view is probably more relevant, where referencing over a large memory footprint can reduce the effectiveness of cache usage. This can have an effect on performance, before extending into virtual memory pageing. 

The other areas for run time improvement could be vectorisation and parallelisation, although these become more difficult to implement in a large simulation application.

There has been little mention of profiling. Where is all the run time occuring ? Typically in simulation modelling that I perform, there are many itterations and the run time bottleneck can be localised to very few routines. This could be investigated.

Scaling up a model from 32-bit to 64-bit can change where the bottlenecks occur. It could well be that the bottleneck in a larger model change and so a new area of modelling needs to be improved.

NotThatItMatters, you have many options to investigate. Hopefully, our suggestions cover the cause of your problems.

John

[jimdempseyatthecove]

NotThatItMatters,

In your subroutine FOO, array A is passed by reference. A(II,JJ,KK) should be processed:

DO K=1,KK
DO J=1,JJ
DO I=1,II

Also, your system has 4GB RAM. Committed shows 10.1/12.6 GB (~4x physical RAM). Nothing inherently wrong with this as long as you reduce page faults. Assume for the sake of argument you had two such arrays A(II,JJ,KK) and B(II,JJ,KK) each 4GB (8GB of your 10GB). An example would be for II=JJ=KK=1600. Virtual Memory on Intel64 can be set to use either 4KB page size or 4MB page size. Lower memory (physical RAM) systems tend to use 4KB page size. The paging system may page one page at a time or multiple pages at a time. Regardless of this, the two arrays (A, B) require 4GB more than fits in RAM. A simple A=B could require between 4GB and 8GB of disk I/O. At 100MB/s this one statement could take 40 to 80 seconds, at 1000MB/s 4 to 8 seconds. I do not know your disk system.

Many operations on such arrays may be such that a smaller array X interacts with the larger array A. In these cases you want to structure to run through X in your inner loops while advancing through A in the outer loops. I this manner you will reduce paging to at most one pass through A (4GB). With A in inner loops and X in outer, you may require on an order of SIZE(X) passes through A (10's, 100's, ... more paging).

If you are performing rather standard functions, consider using something like Intel's MKL. This library is well written for cache locality, and which has the side effect of being page file efficient.

On a different forum there was something else touched upon. The user was having an application crash with out of memory when the allocations were well within the limitations of the system. This would occur late in the run of a program. The behavior looked like a memory leak. Running diagnostics showed the program had no memory leak. At issue was the system page file was being consumed. As it turned out it was not by the application, but rather by a "feature" of Windows where it would buffer writes into RAM (virtual), and at some point this went into page file. Although for your situation you are not experiencing out of memory, this too can greatly agrivate paging latencies. Fortunately there is a way you can turn off this feature (I do not recall the specifics on this).

Jim Dempsey

[SergeyKostrov]

It is a good note. >>... At issue was the system page file was being consumed... Windows VM Manager extends a size of VM paging file until it reaches Maximum Size defined in System applet of Control Panel. I usually set that value at least 4x of an amount of Physical Memory ( PM ). For example, on a system with 32GB of PM that value is 128GB for VM. Then, allocation of 96GB is Not a problem in that case, however a processing is very slow and it is similar to the initial problem of the thread.

[Bernard]

Instead on relying on slow paged memory albeit on SSD drive better option is rto invest in additional RAM.Overhead of thousands I/O operations is performed in kernel mode and extensive context switching can be reduced with more physical memory added to the system

[NotThatItMatters]

Thank you all for your help.  I now have some possibilities.  As a first step, I will attempt to re-index the big arrays from [fortran]A(IJK, 3, 3)[/fortran] to [fortran]A(3, 3, IJK)[/fortran]This way the 3x3 array multiplication, such as matrix inversion and the like, will be handled in contiguous memory.  That in itself may have a marked effect on performance.

As far as suggestions go for increasing RAM and the like, you must realize that what I am simulating is a test, and the software itself goes out to clients with many operating systems and RAM sets.  I would like to have this model run in a stable environment without much extension so that I can be assured that when our clients run similar models on machines without amazing cache or memory, they can run them without too much trouble.

[John_Campbell]

NotThatItMatters,

The change to A(3,3,ijk) should have a significant effect, both for moderate (cache) and large size memory (paging) usage. I'd be interested to find out if this is effective.
You might also find Resource Monitor (a button in task mamager) provides more info as the program runs.
My Subscript-ver2.f90 gave a simple example of timing both CPU and elapsed time. Generating logs of run time { open (unit=99, file='runtime.log', position='append') } could provide a useful log to compare changes. Make sure you include notes in runtime.log of what each run tested, as it's easy to forget what you changed.

Let us know how you go.

John

[SergeyKostrov]

Sorry for a short follow up. Attached is a zip file ( MemTestApp.zip ) with sources of a very simple test application and it allows to allocate different amounts of memory. Even if it is implemented in C/C++ please don't be afraid to use it and let me know if you have any questions. I used that application a lot during an initial phase of porting 32-bit codes to a 64-bit platform because I wanted to see how memory management is working for extreme cases ( for example, allocation of memory blocks larger than 64GB ).

[NotThatItMatters]

The changing from A(IJK, 3, 3) to A(3, 3, IJK) has been implemented (it took a large bit of rewrite).  I am testing it on a large model with x64 CPU.  It is doing "better" than the original, but not great.  It is improving things by a factor of 2.5 to 1.  That still means that for every second of CPU time there are 10+ seconds of connect time.  Reading through these posts, I am wondering if increasing page size or cache might improve things.  I have no insight into this, but I suppose I might expect marginal improvement.