MitchAlsup wrote:
> On Wednesday, September 8, 2021 at 8:49:10 AM UTC-5, EricP wrote:
>> Anton Ertl wrote:
>>> Stephen Fuld <sf...@alumni.cmu.edu.invalid> writes:
>>>> I haven't given any thought at all to what the situation is on an X86
>>>> CPU with fixed length block disks, etc. Remember, these instructions
>>>> are S/360 descendants specific.
>>> I am not limiting myself to S/360 descendants just because they have
>>> such instructions. If I can solve the problem just as effectively
>>> with AMD64-based servers, there is no need for specialized hardware.
>> Sort-merge might make use of general HW scatter-gather DMA mechanism
>> integrated with IO so records are gathered during the disk write operation.
>>
>> Rather than sort records by moving them, sort a vector of descriptors.
>> Then pass this sorted vector containing virtual address and length of each
>> item to the IO write. IO translates each virtual descriptor to one or more
>> physical descriptors, because records can straddle physical pages.
>> Then pass this physical fragment descriptor vector directly to the
>> disk DMA device so it can stream the record fragments directly
>> to sequential disk blocks in one long write.
>>
>> In other words, the physical descriptor vector acts like an IOMMU
>> but for arbitrary byte length fragments rather than whole pages.
> <
> But if you already HAVE an I/O MMU, then you just need the virtual
> address and length (into an address space) and simply program the
> I/O using virtual. The fact any given record straddles a page boundary
> is then not exposed until DMA actually crosses the page boundary.
> <
> This should save a bunch of analysis and copying prior to performing
> the I/O.

Even better if the IOMMU can reuse the same page tables.
Relatively straight forward for hierarchical tables.
I don't know about zSeries inverted page tables.

An IO would just require checking that each referenced
page was resident, fault it in if not, then pin it.
If all the original records were together in a contiguous buffer,
and all the fragment descriptors are in a contiguous vector,
this is straight forward.

The device DMA could use the client process virtual addresses directly
for indexing the descriptor vector and accessing the fragments,
with translation on the fly by the IOMMU.

>> Using multiple buffers, async IO, multiple SMP threads,
>> cache-aware sorts on multiple cores,
>> one could really go to town on concurrency for this.

On Wednesday, September 8, 2021 at 12:11:24 PM UTC-5, EricP wrote:
> MitchAlsup wrote:
> > On Wednesday, September 8, 2021 at 8:49:10 AM UTC-5, EricP wrote:
> >> Anton Ertl wrote:
> >>> Stephen Fuld <sf...@alumni.cmu.edu.invalid> writes:
> >>>> I haven't given any thought at all to what the situation is on an X86
> >>>> CPU with fixed length block disks, etc. Remember, these instructions
> >>>> are S/360 descendants specific.
> >>> I am not limiting myself to S/360 descendants just because they have
> >>> such instructions. If I can solve the problem just as effectively
> >>> with AMD64-based servers, there is no need for specialized hardware.
> >> Sort-merge might make use of general HW scatter-gather DMA mechanism
> >> integrated with IO so records are gathered during the disk write operation.
> >>
> >> Rather than sort records by moving them, sort a vector of descriptors.
> >> Then pass this sorted vector containing virtual address and length of each
> >> item to the IO write. IO translates each virtual descriptor to one or more
> >> physical descriptors, because records can straddle physical pages.
> >> Then pass this physical fragment descriptor vector directly to the
> >> disk DMA device so it can stream the record fragments directly
> >> to sequential disk blocks in one long write.
> >>
> >> In other words, the physical descriptor vector acts like an IOMMU
> >> but for arbitrary byte length fragments rather than whole pages.
> > <
> > But if you already HAVE an I/O MMU, then you just need the virtual
> > address and length (into an address space) and simply program the
> > I/O using virtual. The fact any given record straddles a page boundary
> > is then not exposed until DMA actually crosses the page boundary.
> > <
> > This should save a bunch of analysis and copying prior to performing
> > the I/O.
<
> Even better if the IOMMU can reuse the same page tables.
> Relatively straight forward for hierarchical tables.
> I don't know about zSeries inverted page tables.
<
I don't think the organization of the table matters much, as long as
you start with a virtual address and some association to the address
space in which that virtual address accesses.
<
The modern direction for I/O MMUs is to use the same tables as the
CPUs use. This gives the important property that a virtual address
is a virtual address in the CPU or in the DMA device.
<
About the only things that violate this property are devices without
a full address space (24-bit or 32-bit VASs.) Modern SATA devices
do not have these problems. For these degenerate devices, the
I/O MMU avoids bounce buffers using virtual DMA from the
device virtual address space into the user virtual address space.
>
> An IO would just require checking that each referenced
> page was resident, fault it in if not, then pin it.
> If all the original records were together in a contiguous buffer,
> and all the fragment descriptors are in a contiguous vector,
> this is straight forward.
>
> The device DMA could use the client process virtual addresses directly
> for indexing the descriptor vector and accessing the fragments,
> with translation on the fly by the IOMMU.
<
Exactly
<
> >> Using multiple buffers, async IO, multiple SMP threads,
> >> cache-aware sorts on multiple cores,
> >> one could really go to town on concurrency for this.

According to EricP <ThatWouldBeTelling@thevillage.com>:
>Sort-merge might make use of general HW scatter-gather DMA mechanism
>integrated with IO so records are gathered during the disk write operation.
>
>Rather than sort records by moving them, sort a vector of descriptors.
>Then pass this sorted vector containing virtual address and length of each
>item to the IO write.

The zSeries virtual memory uses conventional page tables with 4K pages and
up to five levels of tables depending on address size. It is not a reverse
map like the POWER's.

The I/O system does not run through the pager and has a separate way
to deal with page mapping. Each I/O command word can point at an array
of indirect addressing words called MIDAW or TIDAW depending on which
generation of I/O architecture it's using. Each IDAW is 16 bytes with
a count and address and some flags. The block that an IDAW points to
cannot cross a page boundary; if it does you need to break it into two
IDAWs.

The point of IDAW was that that application program wrote a channel
program (yes, applications write their own channel programs) with each
command word pointing to an address in virtual memory. The OS then
slightly adjusted the channel instructions by turning on a flag bit to
use IDAWs, and replacing the address in the command word with the
adddress of IDAWs in real memory that point to the physical
address(es) of the page(es) where the data are. Usually one IDAW would
be enough, two if it crossed a page boundary, more only if the block
is so big it crosses into more than two pages. The old I/O system had
a scatter/gather feature called data chaining but it'g gone in the new
system.

Having explained all that, even though you could use the IDAW stuff
for scatter/gather, in practice I think it's only used for backward
compatibility for old programs. Modern systems all integrate the disk
I/O with the pager, so all disk I/O is page sized blocks, 4K in this
case, on 4K boundaries. I am pretty sure that the effort of creating a
set of 16 byte IDAWs for scattered records and then having the OS
check them and split them if a block crosses a page boundary would not
be worth the effort compared to the normal approach of moving the
records into one output buffer and doing one I/O operation to write it
out.

They do support command chaning, so if you had a great big buffer
that filled up 100 pages, it could do one I/O operation to do 100 disk
writes.
--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

EricP wrote:
> Anton Ertl wrote:
>> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>>> I haven't given any thought at all to what the situation is on an X86
>>> CPU with fixed length block disks, etc.  Remember, these instructions
>>> are S/360 descendants specific.
>>
>> I am not limiting myself to S/360 descendants just because they have
>> such instructions.  If I can solve the problem just as effectively
>> with AMD64-based servers, there is no need for specialized hardware.
>
> Sort-merge might make use of general HW scatter-gather DMA mechanism
> integrated with IO so records are gathered during the disk write operation.
>
> Rather than sort records by moving them, sort a vector of descriptors.
> Then pass this sorted vector containing virtual address and length of each
> item to the IO write. IO translates each virtual descriptor to one or more
> physical descriptors, because records can straddle physical pages.
> Then pass this physical fragment descriptor vector directly to the
> disk DMA device so it can stream the record fragments directly
> to sequential disk blocks in one long write.
>
> In other words, the physical descriptor vector acts like an IOMMU
> but for arbitrary byte length fragments rather than whole pages.
>
> Using multiple buffers, async IO, multiple SMP threads,
> cache-aware sorts on multiple cores,
> one could really go to town on concurrency for this.

I did consider that solution, and it would really suck. :-(

The only way to get anything like reasonable speed is by treating all
the disk drives like tape unit, i.e. sequential access only.

The only way I figured out to use key+index in the sorting stage was if
those much smaller records could more or less fit in half the memory,
because then you could sort them, then make another single pass over the
input array while picking up exactly those full records that corresponds
to the first chunk of sorted records. Each such record would be stored
in its calculated target slot, but it would lead to many more disk
passes. :-(

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

According to Stephen Fuld <sfuld@alumni.cmu.edu.invalid>:
>> Sort-merge might make use of general HW scatter-gather DMA mechanism
>> integrated with IO so records are gathered during the disk write operation.
>
>Given that S/360 had the equivalent of scatter/gather (called Data
>Chaining in S/360 parlance), they might very well have used it. As I
>said, I really couldn't find much information on the internal algorithm
>used by IBM's sort program.

Probably not. On low end systems data chaining didn't work very well
because the system sometimes didn't have time to fetch and decode another
CCW in the middle of a disk block. I get the impression it was mostly used
in specific applications like separating the key and the data in ISAM data.

> As I said, I really couldn't find much information on the internal algorithm
> used by IBM's sort program.

http://bitsavers.org/pdf/ibm/360/dos/plm/Y24-5021-0_DOS_Sort_Merge_PLM_Aug66.pdf
http://bitsavers.org/pdf/ibm/370/OS_VS/sort_merge/LY33-8042-6_OS_VS_Sort-Merge_Logic_197909.pdf

Looks to me like they paid a lot of attention to arranging the data on disk
to minimize rotational and seek delay, but they moved the data into the
output buffer, no chaining funny business.
--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

Stephen Fuld wrote:
> On 9/8/2021 6:48 AM, EricP wrote:
>> Anton Ertl wrote:
>>> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>>>> I haven't given any thought at all to what the situation is on an
>>>> X86 CPU with fixed length block disks, etc. Remember, these
>>>> instructions are S/360 descendants specific.
>>>
>>> I am not limiting myself to S/360 descendants just because they have
>>> such instructions. If I can solve the problem just as effectively
>>> with AMD64-based servers, there is no need for specialized hardware.
>>
>> Sort-merge might make use of general HW scatter-gather DMA mechanism
>> integrated with IO so records are gathered during the disk write
>> operation.
>
> Given that S/360 had the equivalent of scatter/gather (called Data
> Chaining in S/360 parlance), they might very well have used it. As I
> said, I really couldn't find much information on the internal algorithm
> used by IBM's sort program.

Would that have been byte fragment chaining or block/page chaining?

VAX 780 had an IOMMU for whole page DMA scatter/gather for block devices.
Certain individual devices could do byte buffer DMA but no chaining.

This would require doing long vectors of byte fragment DMA chaining
across many pages to a block device. Its seems an unusual combination.

Terje Mathisen wrote:
> EricP wrote:
>> Anton Ertl wrote:
>>> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>>>> I haven't given any thought at all to what the situation is on an
>>>> X86 CPU with fixed length block disks, etc. Remember, these
>>>> instructions are S/360 descendants specific.
>>>
>>> I am not limiting myself to S/360 descendants just because they have
>>> such instructions. If I can solve the problem just as effectively
>>> with AMD64-based servers, there is no need for specialized hardware.
>>
>> Sort-merge might make use of general HW scatter-gather DMA mechanism
>> integrated with IO so records are gathered during the disk write
>> operation.
>>
>> Rather than sort records by moving them, sort a vector of descriptors.
>> Then pass this sorted vector containing virtual address and length of
>> each
>> item to the IO write. IO translates each virtual descriptor to one or
>> more
>> physical descriptors, because records can straddle physical pages.
>> Then pass this physical fragment descriptor vector directly to the
>> disk DMA device so it can stream the record fragments directly
>> to sequential disk blocks in one long write.
>>
>> In other words, the physical descriptor vector acts like an IOMMU
>> but for arbitrary byte length fragments rather than whole pages.
>>
>> Using multiple buffers, async IO, multiple SMP threads,
>> cache-aware sorts on multiple cores,
>> one could really go to town on concurrency for this.
>
> I did consider that solution, and it would really suck. :-(

I'm open to that possibility. :-)
But we may be thinking of different scenarios.

> The only way to get anything like reasonable speed is by treating all
> the disk drives like tape unit, i.e. sequential access only.

Right. But the scenarios for two extremes look like

1) a single 1 TB file on a single disk doing an in-place sort

2) a single 1 TB file on a source disk S:,
a single sorted output file on a dest disk D:
and N disks to hold TN temp fragment files.

I'm thinking of the second, I suspect you are thinking of the first.

> The only way I figured out to use key+index in the sorting stage was if
> those much smaller records could more or less fit in half the memory,
> because then you could sort them, then make another single pass over the
> input array while picking up exactly those full records that corresponds
> to the first chunk of sorted records. Each such record would be stored
> in its calculated target slot, but it would lead to many more disk
> passes. :-(
>
> Terje

That sounds like an in place sort.

EricP wrote:
> Stephen Fuld wrote:
>> On 9/8/2021 6:48 AM, EricP wrote:
>>> Anton Ertl wrote:
>>>> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>>>>> I haven't given any thought at all to what the situation is on an
>>>>> X86 CPU with fixed length block disks, etc. Remember, these
>>>>> instructions are S/360 descendants specific.
>>>>
>>>> I am not limiting myself to S/360 descendants just because they have
>>>> such instructions. If I can solve the problem just as effectively
>>>> with AMD64-based servers, there is no need for specialized hardware.
>>>
>>> Sort-merge might make use of general HW scatter-gather DMA mechanism
>>> integrated with IO so records are gathered during the disk write
>>> operation.
>>
>> Given that S/360 had the equivalent of scatter/gather (called Data
>> Chaining in S/360 parlance), they might very well have used it. As I
>> said, I really couldn't find much information on the internal
>> algorithm used by IBM's sort program.
>
> Would that have been byte fragment chaining or block/page chaining?
>
> VAX 780 had an IOMMU for whole page DMA scatter/gather for block devices.
> Certain individual devices could do byte buffer DMA but no chaining.
>
> This would require doing long vectors of byte fragment DMA chaining
> across many pages to a block device. Its seems an unusual combination.

Or maybe not that unusual in an IBM world.
Didn't they used to (and maybe still do) allow users to format
a disk track/cylinder with their own disk sector sizes?
So someone can have a 317 byte disk sector if they want one?

In that environment the DMA hardware probably already supports chaining
DMA fragments with byte length resolution.

On Wednesday, September 8, 2021 at 4:19:27 PM UTC-5, EricP wrote:
> EricP wrote:
> > Stephen Fuld wrote:
> >> On 9/8/2021 6:48 AM, EricP wrote:
> >>> Anton Ertl wrote:
> >>>> Stephen Fuld <sf...@alumni.cmu.edu.invalid> writes:
> >>>>> I haven't given any thought at all to what the situation is on an
> >>>>> X86 CPU with fixed length block disks, etc. Remember, these
> >>>>> instructions are S/360 descendants specific.
> >>>>
> >>>> I am not limiting myself to S/360 descendants just because they have
> >>>> such instructions. If I can solve the problem just as effectively
> >>>> with AMD64-based servers, there is no need for specialized hardware.
> >>>
> >>> Sort-merge might make use of general HW scatter-gather DMA mechanism
> >>> integrated with IO so records are gathered during the disk write
> >>> operation.
> >>
> >> Given that S/360 had the equivalent of scatter/gather (called Data
> >> Chaining in S/360 parlance), they might very well have used it. As I
> >> said, I really couldn't find much information on the internal
> >> algorithm used by IBM's sort program.
> >
> > Would that have been byte fragment chaining or block/page chaining?
> >
> > VAX 780 had an IOMMU for whole page DMA scatter/gather for block devices.
> > Certain individual devices could do byte buffer DMA but no chaining.
> >
> > This would require doing long vectors of byte fragment DMA chaining
> > across many pages to a block device. Its seems an unusual combination.
> Or maybe not that unusual in an IBM world.
> Didn't they used to (and maybe still do) allow users to format
> a disk track/cylinder with their own disk sector sizes?
<
Early 360s did allow for the disk to be formatted the way the customer
wanted his files to appear. Since the mid 1970s when IBM went DASD
(big time) the disks are all formatted in 4KB sectors.
<
IBM build several disk access methods for the older style, but found out
that fixed partitions and a disk cache had significantly greater performance
on many workloads.
<
> So someone can have a 317 byte disk sector if they want one?
<
One can use on older access method (ISAM, VSAM) and appear to get records
the size they want--but the actual I/O takes place in 4KB sizes. The user is
also charged in 4KB chunks of money per unit time.
>
> In that environment the DMA hardware probably already supports chaining
> DMA fragments with byte length resolution.
<
If I recall correctly, the chaining command was "Transfer in Channel"

On Wednesday, September 8, 2021 at 4:04:38 PM UTC-5, EricP wrote:
> Stephen Fuld wrote:
> > On 9/8/2021 6:48 AM, EricP wrote:
> >> Anton Ertl wrote:
> >>> Stephen Fuld <sf...@alumni.cmu.edu.invalid> writes:
> >>>> I haven't given any thought at all to what the situation is on an
> >>>> X86 CPU with fixed length block disks, etc. Remember, these
> >>>> instructions are S/360 descendants specific.
> >>>
> >>> I am not limiting myself to S/360 descendants just because they have
> >>> such instructions. If I can solve the problem just as effectively
> >>> with AMD64-based servers, there is no need for specialized hardware.
> >>
> >> Sort-merge might make use of general HW scatter-gather DMA mechanism
> >> integrated with IO so records are gathered during the disk write
> >> operation.
> >
> > Given that S/360 had the equivalent of scatter/gather (called Data
> > Chaining in S/360 parlance), they might very well have used it. As I
> > said, I really couldn't find much information on the internal algorithm
> > used by IBM's sort program.
> Would that have been byte fragment chaining or block/page chaining?
>
> VAX 780 had an IOMMU for whole page DMA scatter/gather for block devices.
> Certain individual devices could do byte buffer DMA but no chaining.
<
VAX also had 512 Byte pages.
>
> This would require doing long vectors of byte fragment DMA chaining
> across many pages to a block device. Its seems an unusual combination.

According to MitchAlsup <MitchAlsup@aol.com>:
>Early 360s did allow for the disk to be formatted the way the customer
>wanted his files to appear. Since the mid 1970s when IBM went DASD
>(big time) the disks are all formatted in 4KB sectors.
><
>IBM build several disk access methods for the older style, but found out
>that fixed partitions and a disk cache had significantly greater performance
>on many workloads.

Those access methods had to work on machines with tiny memories. You could
get useful work done on a DOS machine in 16K. Once memory got cheap, big
blocks and caches made most of the complicated disk stuff pointless.

>> In that environment the DMA hardware probably already supports chaining
>> DMA fragments with byte length resolution.
><
>If I recall correctly, the chaining command was "Transfer in Channel"

No, TIC was a channel program jump. Command chaining was a sequence of
operatios like a seek followed by a read or sequential reads. Data chaining
was scatter/gather within a single I/O operation.

--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

John Levine <johnl@taugh.com> writes:
> The zSeries virtual memory uses conventional page tables with 4K pages and
> up to five levels of tables depending on address size. It is not a reverse
> map like the POWER's.
>
> The I/O system does not run through the pager and has a separate way
> to deal with page mapping. Each I/O command word can point at an array
> of indirect addressing words called MIDAW or TIDAW depending on which
> generation of I/O architecture it's using. Each IDAW is 16 bytes with
> a count and address and some flags. The block that an IDAW points to
> cannot cross a page boundary; if it does you need to break it into two
> IDAWs.
>
> The point of IDAW was that that application program wrote a channel
> program (yes, applications write their own channel programs) with each
> command word pointing to an address in virtual memory. The OS then
> slightly adjusted the channel instructions by turning on a flag bit to
> use IDAWs, and replacing the address in the command word with the
> adddress of IDAWs in real memory that point to the physical
> address(es) of the page(es) where the data are. Usually one IDAW would
> be enough, two if it crossed a page boundary, more only if the block
> is so big it crosses into more than two pages. The old I/O system had
> a scatter/gather feature called data chaining but it'g gone in the new
> system.
>
> Having explained all that, even though you could use the IDAW stuff
> for scatter/gather, in practice I think it's only used for backward
> compatibility for old programs. Modern systems all integrate the disk
> I/O with the pager, so all disk I/O is page sized blocks, 4K in this
> case, on 4K boundaries. I am pretty sure that the effort of creating a
> set of 16 byte IDAWs for scattered records and then having the OS
> check them and split them if a block crosses a page boundary would not
> be worth the effort compared to the normal approach of moving the
> records into one output buffer and doing one I/O operation to write it
> out.
>
> They do support command chaning, so if you had a great big buffer
> that filled up 100 pages, it could do one I/O operation to do 100 disk
> writes.

IBM 360 implemented scatter/gather with "chained data" CCWs
(... following CCW was only used for data address) ... problem was that
"channel architecture" mandated that channel command words (CCWs) were
strictly serial with no pre-fetching. This was used by (virtual machine)
CP67 simulated channel programs where the virtual channel program
addresses crossing page boundary were contiguous but not their real
address. As devices got faster, there was smaller & smaller window to
fetch the next CCW from processor memory and decode the address. IDAW
introduceed for 370 allowed the IDAW addresses to be prefetched.

It was also used for the >16mbyte real storage hack for 370 3033 that
was still 24bit instruction (both real & virtual) addressing. They
scavenge two unused bits from the 370 16bit page table entry, 12bit page
number, 2 defined bits, 2 undefined bits. The 12bit page number for
4kbyte pages provided for 16mbyte. The hack prepended the two undefined
bits to the 12bit page number ... allowing translation of 24bit virtual
address into 26bit real addressing ... allowing to run with up to
64mbyte real storage.

370 IDALs were 32bit fields and 3033 hack them to read/write 4k pages
located in >16mbyte area. The problem was kernel instructions needing to
access in virtual pages in the >16mbyte area (with real
addresses). Their original "bring down" hack was to write out a 4k page
from the >16mbyte area and read it back in to <16mbyte page slot. I
provided them with a short instruction hack that put the two page
numbers in (reserved) PTEs and running in virtual mode, then did a MVCL
from the virtual page in the >16mbyte area to the virtual page in the
<16mbyte area. It was also used by 3081 with >16mbyte real storage by
customer still running 370 operating systems (before converting to 31bit
operating system).

Decde ago, a customer asked me to track down the decision to move all
370s to virtual memory (initially announce & ship little changed from
360). Old archived post with some from somebody involved
http://www.garlic.com/~lynn/201d.html#73
basically (OS/360) MVT storage management was so bad that the size of
regions for application executed needed to be four times larger than
actually used. As a result, the typical 1mbyte 370/165 only ran with
four execution regions ... and (in part) because disk i/o was so slow,
much larger multiprogramming was needed to utilize the
processor. Mapping MVT to a 16mbyte virtual address space could increase
the number of concurrent execution regions by a factor of four times
with little or no paging.

There was a little bit of code added for this VS2/SVS to create 16mbyte
virtual address space and handle the (infrequent) page operations. The
biggest problem was I/O. Applications did create some of their own
channel programs ... which now had virtual addresses. However, nearly
all channel programs were created by system libraries routines executing
in the application region ... which also now have virtual
addresses. They all would execute EXCP/SVC0 supervisor call to execute
the passed channel program. Now the biggest amount of code moving
MVT->SVC was borrowing CP67 "CCWTRANS" ... which performed that function
for virtual machines running in virtual address space.

As undergraduate in the 60s, I rewrote lots of CP67 code including doing
dynamic adaptive resource manager ... which included what I called
"scheduling to the bottleneck". In the 70s I started noting that
processor speed and amount of real storage was increasing much faster
than disk speed was increasing (needing increaingly larger
multiprogramming levels to keep processors busy). In the early 80s, I
started saying that over the 15years, disk performance relative disk
system throughput had declined by an order of magnitude (10 times,
i.e. systems got 40-50 times faster, disks only got 3-5 times
faster). Disk division executives took exception and assigned the
division performance group to refute my claims. After a couple weeks
they basically came back on said that I had slightly understated the
problem. The performance group then respun the analysis and presented
suggestions for disk optiization strategies at major customer user group
organization.
https://en.wikipedia.org/wiki/SHARE_(computing)

some recent archived posts mentioning their presentation B874 at SHARE
63 (16Aug1984)
http://www.garlic.com/~lynn/2021g.html#44 iBM System/3 FORTRAN for engineering/science work?
http://www.garlic.com/~lynn/2021f.html#53 3380 disk capacity
http://www.garlic.com/~lynn/2021e.html#33 Univac 90/30 DIAG instruction
http://www.garlic.com/~lynn/2021.html#79 IBM Disk Division
http://www.garlic.com/~lynn/2021.html#59 San Jose bldg 50 and 3380 manufacturing
http://www.garlic.com/~lynn/2021.html#17 Performance History, 5-10Oct1986, SEAS
http://www.garlic.com/~lynn/2019d.html#63 IBM 3330 & 3380
http://www.garlic.com/~lynn/2019b.html#94 MVS Boney Fingers
http://www.garlic.com/~lynn/2019.html#78 370 virtual memory
http://www.garlic.com/~lynn/2018e.html#93 It's 1983: What computer would you buy?
http://www.garlic.com/~lynn/2018c.html#30 Bottlenecks and Capacity planning

--
virtualization experience starting Jan1968, online at home since Mar1970

On 9/8/2021 2:52 PM, MitchAlsup wrote:
> On Wednesday, September 8, 2021 at 4:19:27 PM UTC-5, EricP wrote:
>> EricP wrote:
>>> Stephen Fuld wrote:
>>>> On 9/8/2021 6:48 AM, EricP wrote:
>>>>> Anton Ertl wrote:
>>>>>> Stephen Fuld <sf...@alumni.cmu.edu.invalid> writes:
>>>>>>> I haven't given any thought at all to what the situation is on an
>>>>>>> X86 CPU with fixed length block disks, etc. Remember, these
>>>>>>> instructions are S/360 descendants specific.
>>>>>>
>>>>>> I am not limiting myself to S/360 descendants just because they have
>>>>>> such instructions. If I can solve the problem just as effectively
>>>>>> with AMD64-based servers, there is no need for specialized hardware.
>>>>>
>>>>> Sort-merge might make use of general HW scatter-gather DMA mechanism
>>>>> integrated with IO so records are gathered during the disk write
>>>>> operation.
>>>>
>>>> Given that S/360 had the equivalent of scatter/gather (called Data
>>>> Chaining in S/360 parlance), they might very well have used it. As I
>>>> said, I really couldn't find much information on the internal
>>>> algorithm used by IBM's sort program.
>>>
>>> Would that have been byte fragment chaining or block/page chaining?
>>>
>>> VAX 780 had an IOMMU for whole page DMA scatter/gather for block devices.
>>> Certain individual devices could do byte buffer DMA but no chaining.
>>>
>>> This would require doing long vectors of byte fragment DMA chaining
>>> across many pages to a block device. Its seems an unusual combination.
>> Or maybe not that unusual in an IBM world.
>> Didn't they used to (and maybe still do) allow users to format
>> a disk track/cylinder with their own disk sector sizes?
> <
> Early 360s did allow for the disk to be formatted the way the customer
> wanted his files to appear. Since the mid 1970s when IBM went DASD
> (big time) the disks are all formatted in 4KB sectors.

IBM 3390 in the early 1990s was the last "SLED" - Single Large Expensive
Disk, and it did native CKD, so you could indeed have arbitrary sized
blocks on the disk.

As of at least the late 1990s, the transfers between the host CPU and
the disk controller was based on CKD format with arbitrary sized blocks,
up to one 3390 track long. All of the controllers by then were cached,
so transfers were actually between the host and the controller cache.
But the back end disks were essentially industry standard SCSI interface
disks with 512 byte blocks. Actually, some models used a little longer
blocks, say 514 to allow additional checking bytes, though this was
totally hidden from the host. The controller had to do the "mapping"
between the arbitrary record sizes the host expected and the 512 byte
blocks on the disk.

> <
> IBM build several disk access methods for the older style, but found out
> that fixed partitions and a disk cache had significantly greater performance
> on many workloads.
> <
>> So someone can have a 317 byte disk sector if they want one?
> <
> One can use on older access method (ISAM, VSAM) and appear to get records
> the size they want--but the actual I/O takes place in 4KB sizes. The user is
> also charged in 4KB chunks of money per unit time.

I can't speak about charging, but at least in the late 1990s, the 4K
actual I/O wasn't true, at least to/from the actual physical disks.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

EricP wrote:
> Terje Mathisen wrote:
>> EricP wrote:
>>> Anton Ertl wrote:
>>>> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>>>>> I haven't given any thought at all to what the situation is on an
>>>>> X86 CPU with fixed length block disks, etc. Remember, these
>>>>> instructions are S/360 descendants specific.
>>>>
>>>> I am not limiting myself to S/360 descendants just because they have
>>>> such instructions. If I can solve the problem just as effectively
>>>> with AMD64-based servers, there is no need for specialized hardware.
>>>
>>> Sort-merge might make use of general HW scatter-gather DMA mechanism
>>> integrated with IO so records are gathered during the disk write
>>> operation.
>>>
>>> Rather than sort records by moving them, sort a vector of descriptors.
>>> Then pass this sorted vector containing virtual address and length of
>>> each
>>> item to the IO write. IO translates each virtual descriptor to one or
>>> more
>>> physical descriptors, because records can straddle physical pages.
>>> Then pass this physical fragment descriptor vector directly to the
>>> disk DMA device so it can stream the record fragments directly
>>> to sequential disk blocks in one long write.
>>>
>>> In other words, the physical descriptor vector acts like an IOMMU
>>> but for arbitrary byte length fragments rather than whole pages.
>>>
>>> Using multiple buffers, async IO, multiple SMP threads,
>>> cache-aware sorts on multiple cores,
>>> one could really go to town on concurrency for this.
>>
>> I did consider that solution, and it would really suck. :-(
>
> I'm open to that possibility. :-)
> But we may be thinking of different scenarios.
>
>> The only way to get anything like reasonable speed is by treating all
>> the disk drives like tape unit, i.e. sequential access only.
>
> Right. But the scenarios for two extremes look like
>
> 1) a single 1 TB file on a single disk doing an in-place sort
>
> 2) a single 1 TB file on a source disk S:,
> a single sorted output file on a dest disk D:
> and N disks to hold TN temp fragment files.
>
> I'm thinking of the second, I suspect you are thinking of the first.
>
>> The only way I figured out to use key+index in the sorting stage was
>> if those much smaller records could more or less fit in half the
>> memory, because then you could sort them, then make another single
>> pass over the input array while picking up exactly those full records
>> that corresponds to the first chunk of sorted records. Each such
>> record would be stored in its calculated target slot, but it would
>> lead to many more disk passes. :-(
>>
>> Terje
>
> That sounds like an in place sort.

This is what I was thinking, plus the next section "Additional passes"

https://en.wikipedia.org/wiki/External_sorting#External_merge_sort

Combining the "external sort" approach with multiple rotating work buffers,
buffer A is doing an async read, B is sorting, C is async writing.
When all are done, rotate the buffers.
Balance the buffer size, read and write IO times vs sort time.
That keeps 1 cpu/thread and 2 disks busy.

There is some more concurrency to be had as submitting the async
read and write IOs for the large work buffers involves non-trivial work,
pinning pages, allocating IOMMU space, programming IOMMU.
There could be 2 more cpu/threads doing IO prep while one sorts.

The initial source file read is constrained as there is only 1 disk
and our async read-ahead will keep it fully utilized.
By locating the output sort buffers on different disks we don't
have to move the source disk head so reads will be much quicker.

There is the question is how to best utilize N temp disks.
By writing the sort buffers onto N disks, the later merge
can read N disks at once without moving the disk heads.
Again using an A-B-C rotating buffer approach but this time N way,
and writing to a different disk so we don't move the read heads.

Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
> IBM 3390 in the early 1990s was the last "SLED" - Single Large
> Expensive Disk, and it did native CKD, so you could indeed have
> arbitrary sized blocks on the disk.

starting with 3380s ... it was CKD simulated on top of form of fixed
block ... it can be seen where records/track formulas required rounding
up record lengths to a "fixed" cell size.

--
virtualization experience starting Jan1968, online at home since Mar1970

On 9/8/2021 9:22 PM, Stephen Fuld wrote:

Sorry to follow up my own post, but I think I may understand where the
disagreement is.

> On 9/8/2021 2:52 PM, MitchAlsup wrote:

snip

>> Early 360s did allow for the disk to be formatted the way the customer
>> wanted his files to appear. Since the mid 1970s when IBM went DASD
>> (big time) the disks are all formatted in 4KB sectors.
>
> IBM 3390 in the early 1990s was the last "SLED" - Single Large Expensive
> Disk, and it did native CKD, so you could indeed have arbitrary sized
> blocks on the disk.
>
>
> As of at least the late 1990s, the transfers between the host CPU and
> the disk controller was based on CKD format with arbitrary sized blocks,
> up to one 3390 track long.  All of the controllers by then were cached,
> so transfers were actually between the host and the controller cache.
> But the back end disks were essentially industry standard SCSI interface
> disks with 512 byte blocks.  Actually, some models used a little longer
> blocks, say 514 to allow additional checking bytes, though this was
> totally hidden from the host.  The controller had to do the "mapping"
> between the arbitrary record sizes the host expected and the 512 byte
> blocks on the disk.
>
>
>> <
>> IBM build several disk access methods for the older style, but found out
>> that fixed partitions and a disk cache had significantly greater
>> performance
>> on many workloads.
>> <
>>> So someone can have a 317 byte disk sector if they want one?
>> <
>> One can use on older access method (ISAM, VSAM) and appear to get records
>> the size they want--but the actual I/O takes place in 4KB sizes. The
>> user is
>> also charged in 4KB chunks of money per unit time.
>
> I can't speak about charging, but at least in the late 1990s, the 4K
> actual I/O wasn't true, at least to/from the actual physical disks.

I think what Mitch is talking about is the advent of VSAM. Prior access
methods, QSAM, ISAM, BDAM, etc. had the user specify the disk block
size, and indeed many arbitrary sizes were used. My understanding of
VSAM, was that, for at least some uses, it packed individual records
into 4K (or multiple 4K) blocks. So if you had a direct access file,
instead of reading the actual sized record you needed, you read the 4K
block that contained that record, then potentially used information
stored within that block the get to the individual record.

So, to the user, it looked like 4K reads and writes. To the host side
of the disk controller, it looked like any other CKD (actually by that
time ECKD) read or write that just happened to have a length of 4K.

To the back end of the disk controller, it looked just like it did
before. IIRC there were 12 4K records per 3990 track (a 3990 track had
56,664 bytes) and each track had the same count fields etc. that they
always had. And the actual disks were formatted with 512 byte sectors,
some of which (typically more than 4K/512 due to count fields, data
alignment, etc.) were read or written to the disk.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

On 9/9/2021 10:01 AM, Anne & Lynn Wheeler wrote:
> Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>> IBM 3390 in the early 1990s was the last "SLED" - Single Large
>> Expensive Disk, and it did native CKD, so you could indeed have
>> arbitrary sized blocks on the disk.
>
> starting with 3380s ... it was CKD simulated on top of form of fixed
> block ... it can be seen where records/track formulas required rounding
> up record lengths to a "fixed" cell size.

Yes. I can't find the number of bytes per cell on the track, but it was
certainly way less than 4K.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

John Levine wrote:
> According to Stephen Fuld <sfuld@alumni.cmu.edu.invalid>:
>>> Sort-merge might make use of general HW scatter-gather DMA mechanism
>>> integrated with IO so records are gathered during the disk write operation.
>> Given that S/360 had the equivalent of scatter/gather (called Data
>> Chaining in S/360 parlance), they might very well have used it. As I
>> said, I really couldn't find much information on the internal algorithm
>> used by IBM's sort program.
>
> Probably not. On low end systems data chaining didn't work very well
> because the system sometimes didn't have time to fetch and decode another
> CCW in the middle of a disk block. I get the impression it was mostly used
> in specific applications like separating the key and the data in ISAM data.
>
>> As I said, I really couldn't find much information on the internal algorithm
>> used by IBM's sort program.
>
> http://bitsavers.org/pdf/ibm/360/dos/plm/Y24-5021-0_DOS_Sort_Merge_PLM_Aug66.pdf
> http://bitsavers.org/pdf/ibm/370/OS_VS/sort_merge/LY33-8042-6_OS_VS_Sort-Merge_Logic_197909.pdf
>
> Looks to me like they paid a lot of attention to arranging the data on disk
> to minimize rotational and seek delay, but they moved the data into the
> output buffer, no chaining funny business.

This PDF details the SORTL instructions (chapter 26 at the bottom).

The Enhanced-Sort Facility for z/Architecture (SA22-1082-00)
https://www.ibm.com/support/pages/node/6339945
https://www.ibm.com/support/pages/system/files/2020-09/SA22-1082-00.pdf

John Levine wrote:
> According to Stephen Fuld <sfuld@alumni.cmu.edu.invalid>:
>>> Sort-merge might make use of general HW scatter-gather DMA mechanism
>>> integrated with IO so records are gathered during the disk write operation.
>> Given that S/360 had the equivalent of scatter/gather (called Data
>> Chaining in S/360 parlance), they might very well have used it. As I
>> said, I really couldn't find much information on the internal algorithm
>> used by IBM's sort program.
>
> Probably not. On low end systems data chaining didn't work very well
> because the system sometimes didn't have time to fetch and decode another
> CCW in the middle of a disk block. I get the impression it was mostly used
> in specific applications like separating the key and the data in ISAM data.
>
>> As I said, I really couldn't find much information on the internal algorithm
>> used by IBM's sort program.
>
> http://bitsavers.org/pdf/ibm/360/dos/plm/Y24-5021-0_DOS_Sort_Merge_PLM_Aug66.pdf
> http://bitsavers.org/pdf/ibm/370/OS_VS/sort_merge/LY33-8042-6_OS_VS_Sort-Merge_Logic_197909.pdf
>
> Looks to me like they paid a lot of attention to arranging the data on disk
> to minimize rotational and seek delay, but they moved the data into the
> output buffer, no chaining funny business.

This page links to lots of sort documents

DFSORT Product Documentation
DFSORT is IBM's high-performance sort, merge, copy, analysis,
and reporting product. DFSORT is an optional feature of z/OS
https://www.ibm.com/support/pages/node/791985

Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
> Yes. I can't find the number of bytes per cell on the track, but it
> was certainly way less than 4K.

started as 32bytes for 3380 (& 3375) ... somewhat having to do with
error detection/correction technology ... somewhat similar justifying
increasing fixed-block from 512bytes to 4096bytes.
https://en.wikipedia.org/wiki/Fixed-block_architecture
https://en.wikipedia.org/wiki/Advanced_Format

there have been no (physical) CKD made for decades ... currently
being simulated on industry standard fixed-block

trivia: there was a version of mainframe "green card" implemented
in IOS3270 ... which included disk capacity
http://www.garlic.com/~lynn/gcard.html#26.3
and RPS sector formulae
http://www.garlic.com/~lynn/gcard.html#26.4

.... I've done a quick & dirty conversion to html

--
virtualization experience starting Jan1968, online at home since Mar1970

EricP wrote:
> This is what I was thinking, plus the next section "Additional passes"
>
> https://en.wikipedia.org/wiki/External_sorting#External_merge_sort
>
> Combining the "external sort" approach with multiple rotating work buffers,
> buffer A is doing an async read, B is sorting, C is async writing.
> When all are done, rotate the buffers.
> Balance the buffer size, read and write IO times vs sort time.
> That keeps 1 cpu/thread and 2 disks busy.
>
> There is some more concurrency to be had as submitting the async
> read and write IOs for the large work buffers involves non-trivial work,
> pinning pages, allocating IOMMU space, programming IOMMU.
> There could be 2 more cpu/threads doing IO prep while one sorts.
>
> The initial source file read is constrained as there is only 1 disk
> and our async read-ahead will keep it fully utilized.
> By locating the output sort buffers on different disks we don't
> have to move the source disk head so reads will be much quicker.
>
> There is the question is how to best utilize N temp disks.
> By writing the sort buffers onto N disks, the later merge
> can read N disks at once without moving the disk heads.
> Again using an A-B-C rotating buffer approach but this time N way,
> and writing to a different disk so we don't move the read heads.

This is pretty much how I envisioned it, very similar to the N-tapes
merge in Knuth. :-)

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On 9/9/2021 7:14 AM, EricP wrote:

snip

> Combining the "external sort" approach with multiple rotating work buffers,
> buffer A is doing an async read, B is sorting, C is async writing.
> When all are done, rotate the buffers.
> Balance the buffer size, read and write IO times vs sort time.
> That keeps 1 cpu/thread and 2 disks busy.

I am not sure that is the best approach. If you have N bytes of main
memory, you have divided it into three equal sized pieces (in order to
be able to "rotate them". That means the length of the run will be
about 1/3 of what it would be if you used all of the memory as one big
buffer. Read data into that buffer, then sort it, then write it out.

The main determinant of elapsed time in an external sort is the number
of merge passes. As the size of the sorted runs goes up, the number of
passes goes down, and as we discussed in Anton's example, even when you
get to the final merge pass, having fewer runs allows fewer I/Os. So,
yes, you lose concurrency, but the longer runs may gain in elapsed time
by doing less work.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:

> Michael S <already5chosen@yahoo.com> writes:
>
>> Chapter 1. is Tomasulo's S/360 Model 91/191. This chapter was
>> brief. I am not sure how to call it, a failure or a limited
>> success.
>
> It beat the CDC6600, which was it's primary purpose, so in that
> sense it is a success. [...]

The word "it's" is a contraction for "it is".

The possessive form of the word "it" is "its", with no
apostrophe.

It may help to remember that the same rule applies to all
personal pronouns: an apostrophe always indicates a
contraction with "am", "is" or "are" -

I am, we are - I'm, we're
you are - you're
he is, she is, it is, they are - he's, she's, it's, they're

and there is never an apostrophe in the possessive form of a
personal pronoun -

my, our
your
his, hers, its, their

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> It may help to remember that the same rule applies to all
> personal pronouns: an apostrophe always indicates a
> contraction with "am", "is" or "are" -

Except for Bob's name. In this case, "'s" derives from the
older construct "Bob, his...".

Andy Valencia
Home page: https://www.vsta.org/andy/
To contact me: https://www.vsta.org/contact/andy.html

Andy Valencia <vandys@vsta.org> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> It may help to remember that the same rule applies to all
>> personal pronouns: an apostrophe always indicates a
>> contraction with "am", "is" or "are" -
>
> Except for Bob's name. In this case, "'s" derives from the
> older construct "Bob, his...".

The word "Bob" is a noun (more specifically a proper noun, but
still a noun), not a pronoun. For nouns "'s" indicates a
possessive form. The rule above applies only to personal
pronouns.