Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

You're dead, Jim. -- McCoy, "Amok Time", stardate 3372.7


devel / comp.arch / Sequential Consistency

SubjectAuthor
* Sequential ConsistencyMitchAlsup
+- Re: Sequential ConsistencyIvan Godard
+* Re: Sequential ConsistencyThomas Koenig
|`- Re: Sequential ConsistencyEricP
+* Re: Sequential ConsistencyTheo Markettos
|`* Re: Sequential ConsistencyMitchAlsup
| `* Re: Sequential ConsistencyMitchAlsup
|  +* Re: Sequential ConsistencyStephen Fuld
|  |`- Re: Sequential ConsistencyAnton Ertl
|  +* Re: Sequential ConsistencyIvan Godard
|  |+* Re: Sequential ConsistencyQuadibloc
|  ||+* Re: Sequential ConsistencyMitchAlsup
|  |||`- Re: Sequential ConsistencyIvan Godard
|  ||`* Re: Sequential ConsistencyAnton Ertl
|  || `* Re: Sequential ConsistencyStephen Fuld
|  ||  +* Re: Sequential ConsistencyMitchAlsup
|  ||  |`* Re: Sequential ConsistencyQuadibloc
|  ||  | `- Re: Sequential ConsistencyMitchAlsup
|  ||  `- Re: Sequential ConsistencyAnton Ertl
|  |`- Re: Sequential ConsistencyEricP
|  `- Re: Sequential ConsistencyTheo Markettos
`- Re: Sequential ConsistencyTerje Mathisen

1
Sequential Consistency

<e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23826&group=comp.arch#23826

 copy link   Newsgroups: comp.arch
X-Received: by 2002:a5d:534d:0:b0:1ef:956e:320a with SMTP id t13-20020a5d534d000000b001ef956e320amr7494687wrv.613.1646079388683;
Mon, 28 Feb 2022 12:16:28 -0800 (PST)
X-Received: by 2002:a05:6808:2010:b0:2d5:443:2bf2 with SMTP id
q16-20020a056808201000b002d504432bf2mr11979596oiw.30.1646079388191; Mon, 28
Feb 2022 12:16:28 -0800 (PST)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.128.88.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch
Date: Mon, 28 Feb 2022 12:16:27 -0800 (PST)
Injection-Info: google-groups.googlegroups.com; posting-host=2600:1700:291:29f0:61c6:834d:e389:4730;
posting-account=H_G_JQkAAADS6onOMb-dqvUozKse7mcM
NNTP-Posting-Host: 2600:1700:291:29f0:61c6:834d:e389:4730
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>
Subject: Sequential Consistency
From: MitchAl...@aol.com (MitchAlsup)
Injection-Date: Mon, 28 Feb 2022 20:16:28 +0000
Content-Type: text/plain; charset="UTF-8"
 by: MitchAlsup - Mon, 28 Feb 2022 20:16 UTC

It seems to me that when an interconnect performs transmission error
recovery by retransmission that there is no way to ensure sequential
consistency.

For example, 1 CPU spews out 8 STs to device control register in order
to start a STAT read of a disk sector. One of these takes a transport
ECC or CRC error and gets retransmitted; while the rest of the STs
suffer no such failures and arrive in processor order to device. So, by
the time all STs have arrived at device, they are no longer even in
processor order.

Does anyone know how systems deal with this?

Re: Sequential Consistency

<svjbnu$hl9$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23830&group=comp.arch#23830

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: iva...@millcomputing.com (Ivan Godard)
Newsgroups: comp.arch
Subject: Re: Sequential Consistency
Date: Mon, 28 Feb 2022 12:36:15 -0800
Organization: A noiseless patient Spider
Lines: 15
Message-ID: <svjbnu$hl9$1@dont-email.me>
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 28 Feb 2022 20:36:14 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="7ba5d4082cb3d231a79cb55212aa6519";
logging-data="18089"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+9FxY4g9Bj9BvxbRapmkdS"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.6.1
Cancel-Lock: sha1:hwB+UR9PUnSYZHNJbnN6hYIJ2T8=
In-Reply-To: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>
Content-Language: en-US
 by: Ivan Godard - Mon, 28 Feb 2022 20:36 UTC

On 2/28/2022 12:16 PM, MitchAlsup wrote:
> It seems to me that when an interconnect performs transmission error
> recovery by retransmission that there is no way to ensure sequential
> consistency.
>
> For example, 1 CPU spews out 8 STs to device control register in order
> to start a STAT read of a disk sector. One of these takes a transport
> ECC or CRC error and gets retransmitted; while the rest of the STs
> suffer no such failures and arrive in processor order to device. So, by
> the time all STs have arrived at device, they are no longer even in
> processor order.
>
> Does anyone know how systems deal with this?

BSOD

Re: Sequential Consistency

<svjcfl$2ir$1@newsreader4.netcologne.de>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23831&group=comp.arch#23831

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!usenet.goja.nl.eu.org!news.freedyn.de!newsreader4.netcologne.de!news.netcologne.de!.POSTED.2a0a-a540-c7b-0-7285-c2ff-fe6c-992d.ipv6dyn.netcologne.de!not-for-mail
From: tkoe...@netcologne.de (Thomas Koenig)
Newsgroups: comp.arch
Subject: Re: Sequential Consistency
Date: Mon, 28 Feb 2022 20:48:53 -0000 (UTC)
Organization: news.netcologne.de
Distribution: world
Message-ID: <svjcfl$2ir$1@newsreader4.netcologne.de>
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>
Injection-Date: Mon, 28 Feb 2022 20:48:53 -0000 (UTC)
Injection-Info: newsreader4.netcologne.de; posting-host="2a0a-a540-c7b-0-7285-c2ff-fe6c-992d.ipv6dyn.netcologne.de:2a0a:a540:c7b:0:7285:c2ff:fe6c:992d";
logging-data="2651"; mail-complaints-to="abuse@netcologne.de"
User-Agent: slrn/1.0.3 (Linux)
 by: Thomas Koenig - Mon, 28 Feb 2022 20:48 UTC

MitchAlsup <MitchAlsup@aol.com> schrieb:

> It seems to me that when an interconnect performs transmission error
> recovery by retransmission that there is no way to ensure sequential
> consistency.

See https://en.wikipedia.org/wiki/Two_Generals'_Problem :-)

Re: Sequential Consistency

<nLf*530Hy@news.chiark.greenend.org.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23832&group=comp.arch#23832

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!nntp.terraraq.uk!nntp-feed.chiark.greenend.org.uk!ewrotcd!.POSTED!not-for-mail
From: theom+n...@chiark.greenend.org.uk (Theo Markettos)
Newsgroups: comp.arch
Subject: Re: Sequential Consistency
Date: 28 Feb 2022 21:00:21 +0000 (GMT)
Organization: University of Cambridge, England
Lines: 28
Message-ID: <nLf*530Hy@news.chiark.greenend.org.uk>
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>
NNTP-Posting-Host: chiark.greenend.org.uk
X-Trace: chiark.greenend.org.uk 1646082023 7390 212.13.197.229 (28 Feb 2022 21:00:23 GMT)
X-Complaints-To: abuse@chiark.greenend.org.uk
NNTP-Posting-Date: Mon, 28 Feb 2022 21:00:23 +0000 (UTC)
User-Agent: tin/1.8.3-20070201 ("Scotasay") (UNIX) (Linux/3.16.0-11-amd64 (x86_64))
Originator: theom@chiark.greenend.org.uk ([212.13.197.229])
 by: Theo Markettos - Mon, 28 Feb 2022 21:00 UTC

MitchAlsup <MitchAlsup@aol.com> wrote:
> It seems to me that when an interconnect performs transmission error
> recovery by retransmission that there is no way to ensure sequential
> consistency.
>
> For example, 1 CPU spews out 8 STs to device control register in order
> to start a STAT read of a disk sector. One of these takes a transport
> ECC or CRC error and gets retransmitted; while the rest of the STs
> suffer no such failures and arrive in processor order to device. So, by
> the time all STs have arrived at device, they are no longer even in
> processor order.
>
> Does anyone know how systems deal with this?

PCIe has strong ordering by default. It also has a tag word, that's used to
line up requests and responses. It was 5 bits in systems I looked at, but I
think it's been increased to 8 bits. That means you can have up to 32/256
transactions in flight. It technically doesn't care what's in the tag word,
but the link layer guarantees the transactions will be delivered in order -
the tag is just used to align responses with multiple outstanding requests.

There's also a relaxed ordering mode which allows out of order delivery.
That's a flag that has to be set in the PCIe packet.

AXI has a similar strong ordering policy:
https://developer.arm.com/documentation/ihi0022/e/AMBA-AXI3-and-AXI4-Protocol-Specification/Multiple-Transactions/Transaction-ordering?lang=en

Theo

Re: Sequential Consistency

<605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23833&group=comp.arch#23833

 copy link   Newsgroups: comp.arch
X-Received: by 2002:a05:600c:198f:b0:380:fa8f:be22 with SMTP id t15-20020a05600c198f00b00380fa8fbe22mr14613125wmq.43.1646085301009;
Mon, 28 Feb 2022 13:55:01 -0800 (PST)
X-Received: by 2002:a05:6808:15a7:b0:2d4:a0ac:f615 with SMTP id
t39-20020a05680815a700b002d4a0acf615mr12411839oiw.122.1646085300428; Mon, 28
Feb 2022 13:55:00 -0800 (PST)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.128.87.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch
Date: Mon, 28 Feb 2022 13:55:00 -0800 (PST)
In-Reply-To: <nLf*530Hy@news.chiark.greenend.org.uk>
Injection-Info: google-groups.googlegroups.com; posting-host=2600:1700:291:29f0:61c6:834d:e389:4730;
posting-account=H_G_JQkAAADS6onOMb-dqvUozKse7mcM
NNTP-Posting-Host: 2600:1700:291:29f0:61c6:834d:e389:4730
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com> <nLf*530Hy@news.chiark.greenend.org.uk>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com>
Subject: Re: Sequential Consistency
From: MitchAl...@aol.com (MitchAlsup)
Injection-Date: Mon, 28 Feb 2022 21:55:01 +0000
Content-Type: text/plain; charset="UTF-8"
 by: MitchAlsup - Mon, 28 Feb 2022 21:55 UTC

On Monday, February 28, 2022 at 3:00:27 PM UTC-6, Theo Markettos wrote:
> MitchAlsup <Mitch...@aol.com> wrote:
> > It seems to me that when an interconnect performs transmission error
> > recovery by retransmission that there is no way to ensure sequential
> > consistency.
> >
> > For example, 1 CPU spews out 8 STs to device control register in order
> > to start a STAT read of a disk sector. One of these takes a transport
> > ECC or CRC error and gets retransmitted; while the rest of the STs
> > suffer no such failures and arrive in processor order to device. So, by
> > the time all STs have arrived at device, they are no longer even in
> > processor order.
> >
> > Does anyone know how systems deal with this?
> PCIe has strong ordering by default. It also has a tag word, that's used to
> line up requests and responses. It was 5 bits in systems I looked at, but I
> think it's been increased to 8 bits. That means you can have up to 32/256
> transactions in flight. It technically doesn't care what's in the tag word,
> but the link layer guarantees the transactions will be delivered in order -
> the tag is just used to align responses with multiple outstanding requests.
<
So the (re)ordering is applied after retransmission.
<
Thanks.
>
> There's also a relaxed ordering mode which allows out of order delivery.
> That's a flag that has to be set in the PCIe packet.
>
> AXI has a similar strong ordering policy:
> https://developer.arm.com/documentation/ihi0022/e/AMBA-AXI3-and-AXI4-Protocol-Specification/Multiple-Transactions/Transaction-ordering?lang=en
>
> Theo

Re: Sequential Consistency

<ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23834&group=comp.arch#23834

 copy link   Newsgroups: comp.arch
X-Received: by 2002:a5d:50c2:0:b0:1ef:7dc8:dc2f with SMTP id f2-20020a5d50c2000000b001ef7dc8dc2fmr11355634wrt.656.1646092163477;
Mon, 28 Feb 2022 15:49:23 -0800 (PST)
X-Received: by 2002:a05:6830:1b6f:b0:5af:d2f:eed9 with SMTP id
d15-20020a0568301b6f00b005af0d2feed9mr10786684ote.331.1646092162913; Mon, 28
Feb 2022 15:49:22 -0800 (PST)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.128.87.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch
Date: Mon, 28 Feb 2022 15:49:22 -0800 (PST)
In-Reply-To: <605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2600:1700:291:29f0:61c6:834d:e389:4730;
posting-account=H_G_JQkAAADS6onOMb-dqvUozKse7mcM
NNTP-Posting-Host: 2600:1700:291:29f0:61c6:834d:e389:4730
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>
<nLf*530Hy@news.chiark.greenend.org.uk> <605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com>
Subject: Re: Sequential Consistency
From: MitchAl...@aol.com (MitchAlsup)
Injection-Date: Mon, 28 Feb 2022 23:49:23 +0000
Content-Type: text/plain; charset="UTF-8"
 by: MitchAlsup - Mon, 28 Feb 2022 23:49 UTC

On Monday, February 28, 2022 at 3:55:04 PM UTC-6, MitchAlsup wrote:
> On Monday, February 28, 2022 at 3:00:27 PM UTC-6, Theo Markettos wrote:
> > MitchAlsup <Mitch...@aol.com> wrote:
> > > It seems to me that when an interconnect performs transmission error
> > > recovery by retransmission that there is no way to ensure sequential
> > > consistency.
> > >
> > > For example, 1 CPU spews out 8 STs to device control register in order
> > > to start a STAT read of a disk sector. One of these takes a transport
> > > ECC or CRC error and gets retransmitted; while the rest of the STs
> > > suffer no such failures and arrive in processor order to device. So, by
> > > the time all STs have arrived at device, they are no longer even in
> > > processor order.
> > >
> > > Does anyone know how systems deal with this?
> > PCIe has strong ordering by default. It also has a tag word, that's used to
> > line up requests and responses. It was 5 bits in systems I looked at, but I
> > think it's been increased to 8 bits. That means you can have up to 32/256
> > transactions in flight. It technically doesn't care what's in the tag word,
> > but the link layer guarantees the transactions will be delivered in order -
> > the tag is just used to align responses with multiple outstanding requests.
> <
> So the (re)ordering is applied after retransmission.
> <
> Thanks.
<
So, PCIe supports sequential consistency on a per Bus: device, function,
but not between Busses: devices, functions level ?!?
<
A series of writes to one device arrive at device in order, but two or more
series of writes to differing devices arrive at each device in order, but
may arrive at one device out of order with respect to sending order.
<
CPU[c] performs start I/O to 3 devices, by issuing a series of MMI/O
write requests, first to device[1] in its entirety, then to device[2] in its
entirely, then to device[3] in its entirety.
<
However due to retransmission, and bridges; the series of writes
arrive at devices in the order device[3] before device[2] before
device[3].
<
Is this still within sequential consistency ?
> >
> > There's also a relaxed ordering mode which allows out of order delivery.
> > That's a flag that has to be set in the PCIe packet.
> >
> > AXI has a similar strong ordering policy:
> > https://developer.arm.com/documentation/ihi0022/e/AMBA-AXI3-and-AXI4-Protocol-Specification/Multiple-Transactions/Transaction-ordering?lang=en
> >
> > Theo

Re: Sequential Consistency

<svjpm9$rid$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23835&group=comp.arch#23835

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: sfu...@alumni.cmu.edu.invalid (Stephen Fuld)
Newsgroups: comp.arch
Subject: Re: Sequential Consistency
Date: Mon, 28 Feb 2022 16:34:15 -0800
Organization: A noiseless patient Spider
Lines: 58
Message-ID: <svjpm9$rid$1@dont-email.me>
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>
<nLf*530Hy@news.chiark.greenend.org.uk>
<605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com>
<ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 1 Mar 2022 00:34:17 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="82e7169b0d6641a8e6b7d6c5d8cda31b";
logging-data="28237"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/P09N8NluQhfCaZSAK3fuQ/fZh6wUBQD4="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.6.1
Cancel-Lock: sha1:xf4tAcPmk4VsL6WSOU9y5dlzKnA=
In-Reply-To: <ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com>
Content-Language: en-US
 by: Stephen Fuld - Tue, 1 Mar 2022 00:34 UTC

On 2/28/2022 3:49 PM, MitchAlsup wrote:
> On Monday, February 28, 2022 at 3:55:04 PM UTC-6, MitchAlsup wrote:
>> On Monday, February 28, 2022 at 3:00:27 PM UTC-6, Theo Markettos wrote:
>>> MitchAlsup <Mitch...@aol.com> wrote:
>>>> It seems to me that when an interconnect performs transmission error
>>>> recovery by retransmission that there is no way to ensure sequential
>>>> consistency.
>>>>
>>>> For example, 1 CPU spews out 8 STs to device control register in order
>>>> to start a STAT read of a disk sector. One of these takes a transport
>>>> ECC or CRC error and gets retransmitted; while the rest of the STs
>>>> suffer no such failures and arrive in processor order to device. So, by
>>>> the time all STs have arrived at device, they are no longer even in
>>>> processor order.
>>>>
>>>> Does anyone know how systems deal with this?
>>> PCIe has strong ordering by default. It also has a tag word, that's used to
>>> line up requests and responses. It was 5 bits in systems I looked at, but I
>>> think it's been increased to 8 bits. That means you can have up to 32/256
>>> transactions in flight. It technically doesn't care what's in the tag word,
>>> but the link layer guarantees the transactions will be delivered in order -
>>> the tag is just used to align responses with multiple outstanding requests.
>> <
>> So the (re)ordering is applied after retransmission.
>> <
>> Thanks.
> <
> So, PCIe supports sequential consistency on a per Bus: device, function,
> but not between Busses: devices, functions level ?!?
> <
> A series of writes to one device arrive at device in order, but two or more
> series of writes to differing devices arrive at each device in order, but
> may arrive at one device out of order with respect to sending order.
> <
> CPU[c] performs start I/O to 3 devices, by issuing a series of MMI/O
> write requests, first to device[1] in its entirety, then to device[2] in its
> entirely, then to device[3] in its entirety.
> <
> However due to retransmission, and bridges; the series of writes
> arrive at devices in the order device[3] before device[2] before
> device[3].
> <
> Is this still within sequential consistency ?

I don't know about what you call it, but it is certainly typical
behavior. Think of the situation where each device is a disk drive. It
is entirely possible that say the seek for drive 3 is much shorter than
the one for drive 1, so it completes earlier. There is never any
guarantee that the issue order is the same as the completion order of
multiple devices. And, in fact, with command queuing, there isn't a
guarantee that issue order is the same as completion order within
multiple requests for the same device.

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

Re: Sequential Consistency

<svjpo5$qta$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23836&group=comp.arch#23836

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: iva...@millcomputing.com (Ivan Godard)
Newsgroups: comp.arch
Subject: Re: Sequential Consistency
Date: Mon, 28 Feb 2022 16:35:17 -0800
Organization: A noiseless patient Spider
Lines: 46
Message-ID: <svjpo5$qta$1@dont-email.me>
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>
<nLf*530Hy@news.chiark.greenend.org.uk>
<605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com>
<ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 1 Mar 2022 00:35:19 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="4ad2b25809f114bb61ad75419106c4f0";
logging-data="27562"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+rQIgBOTkNd6UJFxgGslLf"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.6.1
Cancel-Lock: sha1:0kx9nmtH16FFGKrtHNQ/6yAwKDU=
In-Reply-To: <ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com>
Content-Language: en-US
 by: Ivan Godard - Tue, 1 Mar 2022 00:35 UTC

On 2/28/2022 3:49 PM, MitchAlsup wrote:
> On Monday, February 28, 2022 at 3:55:04 PM UTC-6, MitchAlsup wrote:
>> On Monday, February 28, 2022 at 3:00:27 PM UTC-6, Theo Markettos wrote:
>>> MitchAlsup <Mitch...@aol.com> wrote:
>>>> It seems to me that when an interconnect performs transmission error
>>>> recovery by retransmission that there is no way to ensure sequential
>>>> consistency.
>>>>
>>>> For example, 1 CPU spews out 8 STs to device control register in order
>>>> to start a STAT read of a disk sector. One of these takes a transport
>>>> ECC or CRC error and gets retransmitted; while the rest of the STs
>>>> suffer no such failures and arrive in processor order to device. So, by
>>>> the time all STs have arrived at device, they are no longer even in
>>>> processor order.
>>>>
>>>> Does anyone know how systems deal with this?
>>> PCIe has strong ordering by default. It also has a tag word, that's used to
>>> line up requests and responses. It was 5 bits in systems I looked at, but I
>>> think it's been increased to 8 bits. That means you can have up to 32/256
>>> transactions in flight. It technically doesn't care what's in the tag word,
>>> but the link layer guarantees the transactions will be delivered in order -
>>> the tag is just used to align responses with multiple outstanding requests.
>> <
>> So the (re)ordering is applied after retransmission.
>> <
>> Thanks.
> <
> So, PCIe supports sequential consistency on a per Bus: device, function,
> but not between Busses: devices, functions level ?!?
> <
> A series of writes to one device arrive at device in order, but two or more
> series of writes to differing devices arrive at each device in order, but
> may arrive at one device out of order with respect to sending order.
> <
> CPU[c] performs start I/O to 3 devices, by issuing a series of MMI/O
> write requests, first to device[1] in its entirety, then to device[2] in its
> entirely, then to device[3] in its entirety.
> <
> However due to retransmission, and bridges; the series of writes
> arrive at devices in the order device[3] before device[2] before
> device[3].
> <
> Is this still within sequential consistency ?

yes
https://en.wikipedia.org/wiki/Sequential_consistency

Re: Sequential Consistency

<05ff4f22-0ae7-471f-b5e8-afaf294bde90n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23838&group=comp.arch#23838

 copy link   Newsgroups: comp.arch
X-Received: by 2002:a05:622a:492:b0:2df:f328:ab2c with SMTP id p18-20020a05622a049200b002dff328ab2cmr12549528qtx.669.1646098341291;
Mon, 28 Feb 2022 17:32:21 -0800 (PST)
X-Received: by 2002:a05:6870:8a25:b0:d7:30b8:9680 with SMTP id
p37-20020a0568708a2500b000d730b89680mr2523973oaq.78.1646098340966; Mon, 28
Feb 2022 17:32:20 -0800 (PST)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch
Date: Mon, 28 Feb 2022 17:32:20 -0800 (PST)
In-Reply-To: <svjpo5$qta$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:56a:fb70:6300:34f1:40a7:6905:52ca;
posting-account=1nOeKQkAAABD2jxp4Pzmx9Hx5g9miO8y
NNTP-Posting-Host: 2001:56a:fb70:6300:34f1:40a7:6905:52ca
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>
<nLf*530Hy@news.chiark.greenend.org.uk> <605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com>
<ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com> <svjpo5$qta$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <05ff4f22-0ae7-471f-b5e8-afaf294bde90n@googlegroups.com>
Subject: Re: Sequential Consistency
From: jsav...@ecn.ab.ca (Quadibloc)
Injection-Date: Tue, 01 Mar 2022 01:32:21 +0000
Content-Type: text/plain; charset="UTF-8"
Lines: 24
 by: Quadibloc - Tue, 1 Mar 2022 01:32 UTC

On Monday, February 28, 2022 at 5:35:23 PM UTC-7, Ivan Godard wrote:
> On 2/28/2022 3:49 PM, MitchAlsup wrote:

> > Is this still within sequential consistency ?

> yes
> https://en.wikipedia.org/wiki/Sequential_consistency

Although from reading the page I couldn't quite see where that
question was settled, it's clear enough that to avoid errors
resulting, all one has to do is make sure that a series of commands
to one I/O device arrives (or, in the presence of errors, is processed)
in the proper order.

Different I/O devices could have different speeds, they could be
waiting on operator actions, they could be accessed by other
processors. So no one expects any constraints on ordering between
them to be enforceable.

Of course, after you've finished reading something from one I/O
device, you can then start writing it to another I/O device. So
one can still have ordering in such a case by the simple expedient
of avoiding all concurrency.

John Savard

Re: Sequential Consistency

<21fd9255-42f5-479f-bec0-71b69229a5afn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23840&group=comp.arch#23840

 copy link   Newsgroups: comp.arch
X-Received: by 2002:a05:622a:10f:b0:2e0:29ea:5ea1 with SMTP id u15-20020a05622a010f00b002e029ea5ea1mr3051500qtw.670.1646099609930;
Mon, 28 Feb 2022 17:53:29 -0800 (PST)
X-Received: by 2002:a05:6808:13d4:b0:2ce:2801:d7bb with SMTP id
d20-20020a05680813d400b002ce2801d7bbmr13505350oiw.44.1646099609719; Mon, 28
Feb 2022 17:53:29 -0800 (PST)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch
Date: Mon, 28 Feb 2022 17:53:29 -0800 (PST)
In-Reply-To: <05ff4f22-0ae7-471f-b5e8-afaf294bde90n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2600:1700:291:29f0:61c6:834d:e389:4730;
posting-account=H_G_JQkAAADS6onOMb-dqvUozKse7mcM
NNTP-Posting-Host: 2600:1700:291:29f0:61c6:834d:e389:4730
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>
<nLf*530Hy@news.chiark.greenend.org.uk> <605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com>
<ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com> <svjpo5$qta$1@dont-email.me>
<05ff4f22-0ae7-471f-b5e8-afaf294bde90n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <21fd9255-42f5-479f-bec0-71b69229a5afn@googlegroups.com>
Subject: Re: Sequential Consistency
From: MitchAl...@aol.com (MitchAlsup)
Injection-Date: Tue, 01 Mar 2022 01:53:29 +0000
Content-Type: text/plain; charset="UTF-8"
Lines: 23
 by: MitchAlsup - Tue, 1 Mar 2022 01:53 UTC

On Monday, February 28, 2022 at 7:32:23 PM UTC-6, Quadibloc wrote:
> On Monday, February 28, 2022 at 5:35:23 PM UTC-7, Ivan Godard wrote:
> > On 2/28/2022 3:49 PM, MitchAlsup wrote:
>
> > > Is this still within sequential consistency ?
<
Now, consider the question of a device accessible through more than one link
{Like a STAT drive that can send/receive data over more than one link} and
because of "stuff" some of the commands are sent over the left link while
others are sent over the right link, and arrive is command-set[3] then [1] then [2].
>
Is this still within sequential consistency ?
Is this a problem that the OS has to guarantee in some manner?
{use link 1 unless it dies. which leads to more questions}
<
Or consider a GPU with 2 daughter cards plugged into 2 PCIe connectors.
Can you write commands to north GPU a command to south GPU and
have any expectation of arrival order?
<
These are not covered in the sequential consistency literature, especially
at Wikipedia level.
<
My question is basically: what are the requirements of sequential consistency
as seen at the receiving end, not at the programming end ??

Re: Sequential Consistency

<vigTJ.43396$8V_7.28664@fx04.iad>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23841&group=comp.arch#23841

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!feeder1.feed.usenet.farm!feed.usenet.farm!peer03.ams4!peer.am4.highwinds-media.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx04.iad.POSTED!not-for-mail
From: ThatWoul...@thevillage.com (EricP)
User-Agent: Thunderbird 2.0.0.24 (Windows/20100228)
MIME-Version: 1.0
Newsgroups: comp.arch
Subject: Re: Sequential Consistency
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com> <svjcfl$2ir$1@newsreader4.netcologne.de>
In-Reply-To: <svjcfl$2ir$1@newsreader4.netcologne.de>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Lines: 44
Message-ID: <vigTJ.43396$8V_7.28664@fx04.iad>
X-Complaints-To: abuse@UsenetServer.com
NNTP-Posting-Date: Tue, 01 Mar 2022 03:20:59 UTC
Date: Mon, 28 Feb 2022 22:20:47 -0500
X-Received-Bytes: 2631
 by: EricP - Tue, 1 Mar 2022 03:20 UTC

Thomas Koenig wrote:
> MitchAlsup <MitchAlsup@aol.com> schrieb:
>
>> It seems to me that when an interconnect performs transmission error
>> recovery by retransmission that there is no way to ensure sequential
>> consistency.
>
> See https://en.wikipedia.org/wiki/Two_Generals'_Problem :-)

The problem for the generals is that they are using asynchronous messaging.
Since you can't know if some intermediary node has not delayed msg transit,
you cannot distinguish between slow and lost msg.
You can only prove that it was not lost when you receive an reply.

The solution for the generals is to use synchronous messaging
with immediate ack/nak. You can verify the the msg was received
correctly by reading back and comparing to what was sent.

In terms of bus hardware, that is a direct write synchronous bus with
address and data byte parity, and immediate ack/nak handshake.
All writable registers are readable without state change.

To ensure all messages are delivered, even ones which are identical
to the immediately prior one, the msg should include a tag bit,
a single bit that sender toggles for each msg.
When you read it back, that tag also must match what you sent.
So two msgs with the value 1234 have tags 0 and 1 and can
therefore be distinguished as both being received.

WRT sequential consistency you not only need to prove multiple msgs
are all delivered, but that they are
(a) delivered once and only once
(b) delivered in the order sent

(a) is ensured by the above synchronous transmit with
read back and tag check.

(b) is ensured by having only one path from sender to receiver
so a read check cannot bypass the msg send.
If there are multiple paths then you must send the read probes
down each path so that no matter which path the send takes,
the read check arrives after the send.

Re: Sequential Consistency

<SdhTJ.75835$%uX7.38179@fx38.iad>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23842&group=comp.arch#23842

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!rocksolid2!i2pn.org!aioe.org!news.uzoreto.com!news-out.netnews.com!news.alt.net!fdc2.netnews.com!peer03.ams1!peer.ams1.xlned.com!news.xlned.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx38.iad.POSTED!not-for-mail
From: ThatWoul...@thevillage.com (EricP)
User-Agent: Thunderbird 2.0.0.24 (Windows/20100228)
MIME-Version: 1.0
Newsgroups: comp.arch
Subject: Re: Sequential Consistency
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com> <nLf*530Hy@news.chiark.greenend.org.uk> <605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com> <ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com> <svjpo5$qta$1@dont-email.me>
In-Reply-To: <svjpo5$qta$1@dont-email.me>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Lines: 73
Message-ID: <SdhTJ.75835$%uX7.38179@fx38.iad>
X-Complaints-To: abuse@UsenetServer.com
NNTP-Posting-Date: Tue, 01 Mar 2022 04:24:18 UTC
Date: Mon, 28 Feb 2022 23:24:08 -0500
X-Received-Bytes: 4074
 by: EricP - Tue, 1 Mar 2022 04:24 UTC

Ivan Godard wrote:
> On 2/28/2022 3:49 PM, MitchAlsup wrote:
>> On Monday, February 28, 2022 at 3:55:04 PM UTC-6, MitchAlsup wrote:
>>> On Monday, February 28, 2022 at 3:00:27 PM UTC-6, Theo Markettos wrote:
>>>> MitchAlsup <Mitch...@aol.com> wrote:
>>>>> It seems to me that when an interconnect performs transmission error
>>>>> recovery by retransmission that there is no way to ensure sequential
>>>>> consistency.
>>>>>
>>>>> For example, 1 CPU spews out 8 STs to device control register in order
>>>>> to start a STAT read of a disk sector. One of these takes a transport
>>>>> ECC or CRC error and gets retransmitted; while the rest of the STs
>>>>> suffer no such failures and arrive in processor order to device.
>>>>> So, by
>>>>> the time all STs have arrived at device, they are no longer even in
>>>>> processor order.
>>>>>
>>>>> Does anyone know how systems deal with this?
>>>> PCIe has strong ordering by default. It also has a tag word, that's
>>>> used to
>>>> line up requests and responses. It was 5 bits in systems I looked
>>>> at, but I
>>>> think it's been increased to 8 bits. That means you can have up to
>>>> 32/256
>>>> transactions in flight. It technically doesn't care what's in the
>>>> tag word,
>>>> but the link layer guarantees the transactions will be delivered in
>>>> order -
>>>> the tag is just used to align responses with multiple outstanding
>>>> requests.
>>> <
>>> So the (re)ordering is applied after retransmission.
>>> <
>>> Thanks.
>> <
>> So, PCIe supports sequential consistency on a per Bus: device, function,
>> but not between Busses: devices, functions level ?!?
>> <
>> A series of writes to one device arrive at device in order, but two or
>> more
>> series of writes to differing devices arrive at each device in order, but
>> may arrive at one device out of order with respect to sending order.
>> <
>> CPU[c] performs start I/O to 3 devices, by issuing a series of MMI/O
>> write requests, first to device[1] in its entirety, then to device[2]
>> in its
>> entirely, then to device[3] in its entirety.
>> <
>> However due to retransmission, and bridges; the series of writes
>> arrive at devices in the order device[3] before device[2] before
>> device[3].
>> <
>> Is this still within sequential consistency ?
>
> yes
> https://en.wikipedia.org/wiki/Sequential_consistency

Careful... multiple paths can break sequential consistency,
especially if there is retransmission.
And a single full duplex link can simulate multiple paths.

S.C. requires the the messages from a single source to a single receiver
be delivered in order, but allows multiple sources to be interleaved.
Three sources A, B, C sending 2 messages each A1,A2, B1,B2, C1,C2
the msgs from each source can be interleaved but must remain in source order.
But multiple pathways can allow A2 to arrive before A1.

Having separate send and receive channels, with the receipt ack/nak
sent back on the receive channel is the same as multiple paths if
you allow msg A2 to be sent before receiving the NAK for prior A1:
it can allow msg A2 to bypass A1 and arrive first.

Re: Sequential Consistency

<svkjuh$ntl$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23844&group=comp.arch#23844

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: iva...@millcomputing.com (Ivan Godard)
Newsgroups: comp.arch
Subject: Re: Sequential Consistency
Date: Tue, 1 Mar 2022 00:02:24 -0800
Organization: A noiseless patient Spider
Lines: 46
Message-ID: <svkjuh$ntl$1@dont-email.me>
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>
<nLf*530Hy@news.chiark.greenend.org.uk>
<605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com>
<ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com>
<svjpo5$qta$1@dont-email.me>
<05ff4f22-0ae7-471f-b5e8-afaf294bde90n@googlegroups.com>
<21fd9255-42f5-479f-bec0-71b69229a5afn@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 1 Mar 2022 08:02:26 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="4ad2b25809f114bb61ad75419106c4f0";
logging-data="24501"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18buUI7uGLU/jx4w/7gpWq8"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.6.1
Cancel-Lock: sha1:F/LnGEnov5BFevFC9jkqNb1LliA=
In-Reply-To: <21fd9255-42f5-479f-bec0-71b69229a5afn@googlegroups.com>
Content-Language: en-US
 by: Ivan Godard - Tue, 1 Mar 2022 08:02 UTC

On 2/28/2022 5:53 PM, MitchAlsup wrote:
> On Monday, February 28, 2022 at 7:32:23 PM UTC-6, Quadibloc wrote:
>> On Monday, February 28, 2022 at 5:35:23 PM UTC-7, Ivan Godard wrote:
>>> On 2/28/2022 3:49 PM, MitchAlsup wrote:
>>
>>>> Is this still within sequential consistency ?
> <
> Now, consider the question of a device accessible through more than one link
> {Like a STAT drive that can send/receive data over more than one link} and
> because of "stuff" some of the commands are sent over the left link while
> others are sent over the right link, and arrive is command-set[3] then [1] then [2].
>>
> Is this still within sequential consistency ?
> Is this a problem that the OS has to guarantee in some manner?
> {use link 1 unless it dies. which leads to more questions}
> <
> Or consider a GPU with 2 daughter cards plugged into 2 PCIe connectors.
> Can you write commands to north GPU a command to south GPU and
> have any expectation of arrival order?
> <
> These are not covered in the sequential consistency literature, especially
> at Wikipedia level.
> <
> My question is basically: what are the requirements of sequential consistency
> as seen at the receiving end, not at the programming end ??

The sink must see messages from each source in the order issued by that
source; messages from multiple sources may be arbitrarily interleaved.

The question above is a matter of definition: if the two streams on the
two paths constitute a single stream that bifurcated then SC has been
violated, but if they form two message streams and order is preserved in
each then there is SC.

It is common to have a single stream (or multiple streams) to be sent
over a connecting mesh such that individual messages have random delay
and the raw received stream gets reordered. The stream order can be
restored by labeling each message with a sequence number and buffering
early-arriving messages. Note that this is an order problem, not a lost
message problem; it is not Two Generals.

Sequence tagging is sufficient in network packets and other systems
where buffering is practical. SC is only an issue with RAM or other
media that are incapable of buffering and order-restore. Two Generals is
not a practical problem; while the probability of loss can never be
zero, it can cheaply be made arbitrarily small.

Re: Sequential Consistency

<svkmb3$m4k$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23845&group=comp.arch#23845

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!aioe.org!UXtAIYUgaw/fkqnS/V28xg.user.46.165.242.91.POSTED!not-for-mail
From: terje.ma...@tmsw.no (Terje Mathisen)
Newsgroups: comp.arch
Subject: Re: Sequential Consistency
Date: Tue, 1 Mar 2022 09:43:23 +0100
Organization: Aioe.org NNTP Server
Message-ID: <svkmb3$m4k$1@gioia.aioe.org>
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="22676"; posting-host="UXtAIYUgaw/fkqnS/V28xg.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101
Firefox/68.0 SeaMonkey/2.53.10.2
X-Notice: Filtered by postfilter v. 0.9.2
 by: Terje Mathisen - Tue, 1 Mar 2022 08:43 UTC

MitchAlsup wrote:
> It seems to me that when an interconnect performs transmission error
> recovery by retransmission that there is no way to ensure sequential
> consistency.
>
> For example, 1 CPU spews out 8 STs to device control register in order
> to start a STAT read of a disk sector. One of these takes a transport
> ECC or CRC error and gets retransmitted; while the rest of the STs
> suffer no such failures and arrive in processor order to device. So, by
> the time all STs have arrived at device, they are no longer even in
> processor order.
>
> Does anyone know how systems deal with this?
>
Don't do it?

I.e. require the command packet to be completely loaded before the final
DOIT register gets a write?

(I'm assuming memory-mapped IO, with a command buffer and some way to
specify that the command packet is complete.)

Terje

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

Re: Sequential Consistency

<2022Mar1.102542@mips.complang.tuwien.ac.at>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23848&group=comp.arch#23848

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ant...@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.arch
Subject: Re: Sequential Consistency
Date: Tue, 01 Mar 2022 09:25:42 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 70
Message-ID: <2022Mar1.102542@mips.complang.tuwien.ac.at>
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com> <nLf*530Hy@news.chiark.greenend.org.uk> <605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com> <ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com> <svjpm9$rid$1@dont-email.me>
Injection-Info: reader02.eternal-september.org; posting-host="1b13e76e53be42b0a18a8b2bfc514b6e";
logging-data="25017"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX180PmDhNrJG+9pBKD/p7PCi"
Cancel-Lock: sha1:ngHVteBk/u6FEMZ9BG4kjohMHB4=
X-newsreader: xrn 10.00-beta-3
 by: Anton Ertl - Tue, 1 Mar 2022 09:25 UTC

Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>On 2/28/2022 3:49 PM, MitchAlsup wrote:
>> However due to retransmission, and bridges; the series of writes
>> arrive at devices in the order device[3] before device[2] before
>> device[3].
>> <
>> Is this still within sequential consistency ?

Depends on whether something can see this reordering. Assuming
something can, it is not. The next question is how to fix this (if we
want to, and I think we should want to).

> And, in fact, with command queuing, there isn't a
>guarantee that issue order is the same as completion order within
>multiple requests for the same device.

Command queuing protocols are obviously intended to provide a more
complicated programming model than sequential consistency. Given that
the Unix system call interface to files provides a mostly sequentially
consistent interface, the file system has to make up for this.

One interesting aspect in this area is that consumer (and maybe these
days all) disk drives come configured to perform volatile write
caching when using the simpler synchronous interface instead of
command queuing. This gives you sequential consistency within the
drive and acceptable performance, but not persistence (consistency in
case of, e.g., a power outage). This agrees nicely with POSIX, which
does not standardize the behaviour in such cases; but as a user, I
prefer that my data does not vanish on a power outage.

File systems try to provide persistence (to varying degrees) and
performance, which means either combining the non-persistent writes
with barriers (providing an ordering guarantee) or syncs (providing a
persistence guarantee), or to use an asynchronous interface like
tagged commands (which also support barriers and syncs in NCQ, but
that could be handled instead by waiting for the completion of the
appropriate writes on the CPU side).

Concerning the various degrees of file system persistence, there are
again similar consistency models to what we see at other levels:

* strict consistency: all writes are synchronous. This is often used
as straw man by advocates of file systems that provide weak
consistency.

* sequential consistency: Writes by all processes are persisted on
disk in an order consistent with what POSIX guarantees for the
non-crashing case. The persistence may be delayed wrt the visible
effects, so in case of a power outage you may find that you have
lost some seconds of work. If you need a persistence guarantee
(e.g., for reporting a completed transaction to a remote client),
you can get it with a synchronous sync(). The performance advantage
of this model over strict consistency is that the writing processes
don't need to wait for the writes to complete, and that mutiple
writes can be batched together.

* weak consistency: The file system (e.g., ext4) typically does not
guarantee any persistence. It's developer claims that any lack of
persistence is not the file system's fault, but the application's
fault for not having used enough calls to fsync() or fdatasync().
Of course there is no good way to be sure that you have enough of
these calls; moreover, these calls are so slow that application
writers want to minimize their usage.

* no persistence: RAMdisks.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Re: Sequential Consistency

<2022Mar1.114449@mips.complang.tuwien.ac.at>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23849&group=comp.arch#23849

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ant...@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.arch
Subject: Re: Sequential Consistency
Date: Tue, 01 Mar 2022 10:44:49 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 20
Message-ID: <2022Mar1.114449@mips.complang.tuwien.ac.at>
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com> <nLf*530Hy@news.chiark.greenend.org.uk> <605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com> <ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com> <svjpo5$qta$1@dont-email.me> <05ff4f22-0ae7-471f-b5e8-afaf294bde90n@googlegroups.com>
Injection-Info: reader02.eternal-september.org; posting-host="1b13e76e53be42b0a18a8b2bfc514b6e";
logging-data="25017"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+Tk65lYt0ekuwTJYFxckrS"
Cancel-Lock: sha1:DU2ZuyBwgn/VIeCAFR2kWKqKCKc=
X-newsreader: xrn 10.00-beta-3
 by: Anton Ertl - Tue, 1 Mar 2022 10:44 UTC

Quadibloc <jsavard@ecn.ab.ca> writes:
>Different I/O devices could have different speeds, they could be
>waiting on operator actions, they could be accessed by other
>processors. So no one expects any constraints on ordering between
>them to be enforceable.

Why should no one expect that? I think that hardware designers should
not expect software to make up for hardware's deficiencies. Most of
the time when hardware designers were lazy and threw the problem over
to software, that hardware was not very successful. Among the more
successful examples are IA-64 and the Cell Broadband Engine.
Conversely, AMD64 is not so successful because it is so pure and
beautiful, but because it made itself easy for software at every step
of the journey, starting from the 8086 being assembly-language
compatible with the 8080.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Re: Sequential Consistency

<svlj1h$rp5$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23853&group=comp.arch#23853

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: sfu...@alumni.cmu.edu.invalid (Stephen Fuld)
Newsgroups: comp.arch
Subject: Re: Sequential Consistency
Date: Tue, 1 Mar 2022 08:53:05 -0800
Organization: A noiseless patient Spider
Lines: 35
Message-ID: <svlj1h$rp5$1@dont-email.me>
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>
<nLf*530Hy@news.chiark.greenend.org.uk>
<605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com>
<ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com>
<svjpo5$qta$1@dont-email.me>
<05ff4f22-0ae7-471f-b5e8-afaf294bde90n@googlegroups.com>
<2022Mar1.114449@mips.complang.tuwien.ac.at>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 1 Mar 2022 16:53:05 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="94bb487caa48afe4a02df1abaf930143";
logging-data="28453"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/EdtoQhAJ7+AepjMNQYrgKik7UkbFbpsI="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.6.1
Cancel-Lock: sha1:kx2lG79Vp14WqRJOGUWvbm69ya8=
In-Reply-To: <2022Mar1.114449@mips.complang.tuwien.ac.at>
Content-Language: en-US
 by: Stephen Fuld - Tue, 1 Mar 2022 16:53 UTC

On 3/1/2022 2:44 AM, Anton Ertl wrote:
> Quadibloc <jsavard@ecn.ab.ca> writes:
>> Different I/O devices could have different speeds, they could be
>> waiting on operator actions, they could be accessed by other
>> processors. So no one expects any constraints on ordering between
>> them to be enforceable.
>
> Why should no one expect that? I think that hardware designers should
> not expect software to make up for hardware's deficiencies. Most of
> the time when hardware designers were lazy and threw the problem over
> to software, that hardware was not very successful. Among the more
> successful examples are IA-64 and the Cell Broadband Engine.
> Conversely, AMD64 is not so successful because it is so pure and
> beautiful, but because it made itself easy for software at every step
> of the journey, starting from the 8086 being assembly-language
> compatible with the 8080.

You have switched the domain (or at least greatly enlarged it) over what
John was talking about. It is clear from his first sentence that he is
talking about I/O devices, and in that realm I absolutely agree that no
one expects I/O completions on different devices to be in the same order
as their respective initiations. And they shouldn't.

Do you really want some hardware that communicates among multiple
independent I/O devices to insure that an I/O initialed to one doesn't
complete until an earlier I/O initiated to another device? I find it
hard to believe that you think that is a better solution.

Yes, it does make the software a little more complicated for situations
where that is required, e.g. database logs, but software has been able
to handle that for decades.

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

Re: Sequential Consistency

<1bff1203-ff18-4a89-ad13-76f587f24cd9n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23856&group=comp.arch#23856

 copy link   Newsgroups: comp.arch
X-Received: by 2002:a37:644:0:b0:60d:eace:79c1 with SMTP id 65-20020a370644000000b0060deace79c1mr14178164qkg.744.1646159598088;
Tue, 01 Mar 2022 10:33:18 -0800 (PST)
X-Received: by 2002:a9d:6a44:0:b0:5af:1886:86ec with SMTP id
h4-20020a9d6a44000000b005af188686ecmr13470977otn.333.1646159597941; Tue, 01
Mar 2022 10:33:17 -0800 (PST)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch
Date: Tue, 1 Mar 2022 10:33:17 -0800 (PST)
In-Reply-To: <svlj1h$rp5$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=2600:1700:291:29f0:68b9:546f:8e1c:46cb;
posting-account=H_G_JQkAAADS6onOMb-dqvUozKse7mcM
NNTP-Posting-Host: 2600:1700:291:29f0:68b9:546f:8e1c:46cb
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>
<nLf*530Hy@news.chiark.greenend.org.uk> <605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com>
<ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com> <svjpo5$qta$1@dont-email.me>
<05ff4f22-0ae7-471f-b5e8-afaf294bde90n@googlegroups.com> <2022Mar1.114449@mips.complang.tuwien.ac.at>
<svlj1h$rp5$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <1bff1203-ff18-4a89-ad13-76f587f24cd9n@googlegroups.com>
Subject: Re: Sequential Consistency
From: MitchAl...@aol.com (MitchAlsup)
Injection-Date: Tue, 01 Mar 2022 18:33:18 +0000
Content-Type: text/plain; charset="UTF-8"
Lines: 39
 by: MitchAlsup - Tue, 1 Mar 2022 18:33 UTC

On Tuesday, March 1, 2022 at 10:53:08 AM UTC-6, Stephen Fuld wrote:
> On 3/1/2022 2:44 AM, Anton Ertl wrote:
> > Quadibloc <jsa...@ecn.ab.ca> writes:
> >> Different I/O devices could have different speeds, they could be
> >> waiting on operator actions, they could be accessed by other
> >> processors. So no one expects any constraints on ordering between
> >> them to be enforceable.
> >
> > Why should no one expect that? I think that hardware designers should
> > not expect software to make up for hardware's deficiencies. Most of
> > the time when hardware designers were lazy and threw the problem over
> > to software, that hardware was not very successful. Among the more
> > successful examples are IA-64 and the Cell Broadband Engine.
> > Conversely, AMD64 is not so successful because it is so pure and
> > beautiful, but because it made itself easy for software at every step
> > of the journey, starting from the 8086 being assembly-language
> > compatible with the 8080.
> You have switched the domain (or at least greatly enlarged it) over what
> John was talking about. It is clear from his first sentence that he is
> talking about I/O devices, and in that realm I absolutely agree that no
> one expects I/O completions on different devices to be in the same order
> as their respective initiations. And they shouldn't.
>
> Do you really want some hardware that communicates among multiple
> independent I/O devices to insure that an I/O initialed to one doesn't
> complete until an earlier I/O initiated to another device? I find it
> hard to believe that you think that is a better solution.
<
You already don't get result delivery in instruction order in pipelined
FPUs, consider FADD versus FDIV.
<
On the other hand, HW goes through lots of hassle to provide precise
exceptions................all to give the illusion of a single point of control.
>
> Yes, it does make the software a little more complicated for situations
> where that is required, e.g. database logs, but software has been able
> to handle that for decades.
> --
> - Stephen Fuld
> (e-mail address disguised to prevent spam)

Re: Sequential Consistency

<2022Mar1.193533@mips.complang.tuwien.ac.at>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23857&group=comp.arch#23857

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ant...@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.arch
Subject: Re: Sequential Consistency
Date: Tue, 01 Mar 2022 18:35:33 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 53
Message-ID: <2022Mar1.193533@mips.complang.tuwien.ac.at>
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com> <nLf*530Hy@news.chiark.greenend.org.uk> <605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com> <ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com> <svjpo5$qta$1@dont-email.me> <05ff4f22-0ae7-471f-b5e8-afaf294bde90n@googlegroups.com> <2022Mar1.114449@mips.complang.tuwien.ac.at> <svlj1h$rp5$1@dont-email.me>
Injection-Info: reader02.eternal-september.org; posting-host="1b13e76e53be42b0a18a8b2bfc514b6e";
logging-data="24604"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/cW8xm1dbpokZpxLbFanSQ"
Cancel-Lock: sha1:iibuFXg8ekjQ32v890+l7xiq78s=
X-newsreader: xrn 10.00-beta-3
 by: Anton Ertl - Tue, 1 Mar 2022 18:35 UTC

Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>On 3/1/2022 2:44 AM, Anton Ertl wrote:
>> Quadibloc <jsavard@ecn.ab.ca> writes:
>>> Different I/O devices could have different speeds, they could be
>>> waiting on operator actions, they could be accessed by other
>>> processors. So no one expects any constraints on ordering between
>>> them to be enforceable.
>>
>> Why should no one expect that? I think that hardware designers should
>> not expect software to make up for hardware's deficiencies.
....
>You have switched the domain (or at least greatly enlarged it) over what
>John was talking about.

Certainly. It's a knee-jerk reaction to the blinders that he puts on
and that he may impose on his readers by claiming that "no one expects
....". "No one" (except Hwu, Patt, and Shebanow) expected OoO to take
off in the 1980s, "no one" expected precise exceptions, etc. But in
these instances a few people took off the blinders and found
solutions, and the solutions took over the world.

>It is clear from his first sentence that he is
>talking about I/O devices, and in that realm I absolutely agree that no
>one expects I/O completions on different devices to be in the same order
>as their respective initiations. And they shouldn't.
>
>Do you really want some hardware that communicates among multiple
>independent I/O devices to insure that an I/O initialed to one doesn't
>complete until an earlier I/O initiated to another device? I find it
>hard to believe that you think that is a better solution.

We certainly do it that way for OoO execution, where we may keep the
result of an instruction in the ROB for hundreds of cycles until all
the logically earlier instructions commit, before we commit that
instruction (but we can use its result earlier).

I have not had much to do with I/O programming, so I cannot say how
much of a problem hardware designer lazyness is there, and how much
better that software would be if the hardware were better, so maybe
the current model is good enough.

>Yes, it does make the software a little more complicated for situations
>where that is required, e.g. database logs, but software has been able
>to handle that for decades.

I am not so sure. E.g., in Linux file systems wanted or should use
barriers, but some block devices (e.g., LVM IIRC) did not implement
them. Not all is well in I/O land.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Re: Sequential Consistency

<d58000c6-a6fc-489e-8633-934083558a93n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23858&group=comp.arch#23858

 copy link   Newsgroups: comp.arch
X-Received: by 2002:a37:311:0:b0:648:c4dc:f9f2 with SMTP id 17-20020a370311000000b00648c4dcf9f2mr14521601qkd.500.1646162524253;
Tue, 01 Mar 2022 11:22:04 -0800 (PST)
X-Received: by 2002:a9d:72c6:0:b0:5af:42ef:bb7c with SMTP id
d6-20020a9d72c6000000b005af42efbb7cmr13249982otk.96.1646162524017; Tue, 01
Mar 2022 11:22:04 -0800 (PST)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch
Date: Tue, 1 Mar 2022 11:22:03 -0800 (PST)
In-Reply-To: <1bff1203-ff18-4a89-ad13-76f587f24cd9n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:56a:fb70:6300:883:6219:3bd2:c95e;
posting-account=1nOeKQkAAABD2jxp4Pzmx9Hx5g9miO8y
NNTP-Posting-Host: 2001:56a:fb70:6300:883:6219:3bd2:c95e
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>
<nLf*530Hy@news.chiark.greenend.org.uk> <605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com>
<ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com> <svjpo5$qta$1@dont-email.me>
<05ff4f22-0ae7-471f-b5e8-afaf294bde90n@googlegroups.com> <2022Mar1.114449@mips.complang.tuwien.ac.at>
<svlj1h$rp5$1@dont-email.me> <1bff1203-ff18-4a89-ad13-76f587f24cd9n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <d58000c6-a6fc-489e-8633-934083558a93n@googlegroups.com>
Subject: Re: Sequential Consistency
From: jsav...@ecn.ab.ca (Quadibloc)
Injection-Date: Tue, 01 Mar 2022 19:22:04 +0000
Content-Type: text/plain; charset="UTF-8"
Lines: 33
 by: Quadibloc - Tue, 1 Mar 2022 19:22 UTC

On Tuesday, March 1, 2022 at 11:33:20 AM UTC-7, MitchAlsup wrote:

> You already don't get result delivery in instruction order in pipelined
> FPUs, consider FADD versus FDIV.

> On the other hand, HW goes through lots of hassle to provide precise
> exceptions................all to give the illusion of a single point of control.

To me, that asks the question: can we do without the illusion of a
single point of control?

Some instruction sets had branch instructions that didn't branch until
after the following instruction or two was executed. So I guess you could
have a divide instruction that had delay slots too.

Precise exceptions were desired so that if something went wrong in
a program, it was known where it went wrong, so that an interrupt
routine could presumably fix it. This could be done without a pipelined
computer pretending not to be pipelined, the interrupt would just have,
instead of a return address, a lengthy discription of where everything
happened to be in flight when the exception occurred.

Of course, there are _good_ reasons why that hasn't even been tried.

But in a way, this seems to me to be a pointless discussion. Of course
we could say that out-of-order execution is wicked, and instead we
should have a larger number of in-order cores for the same throughput
without these issues and wasted transistors.

But because we don't have the magic solution for parallel programming,
and probably never will, the cost for that is higher latency. Sometimes,
even if not as often as people seem to think, that matters.

John Savard

Re: Sequential Consistency

<2d314f4b-7f8b-4382-9cfa-a96881769fe9n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23859&group=comp.arch#23859

 copy link   Newsgroups: comp.arch
X-Received: by 2002:ad4:5bee:0:b0:432:f52d:28b6 with SMTP id k14-20020ad45bee000000b00432f52d28b6mr10130179qvc.44.1646163224669;
Tue, 01 Mar 2022 11:33:44 -0800 (PST)
X-Received: by 2002:a05:6808:2010:b0:2d5:443:2bf2 with SMTP id
q16-20020a056808201000b002d504432bf2mr16084784oiw.30.1646163224420; Tue, 01
Mar 2022 11:33:44 -0800 (PST)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch
Date: Tue, 1 Mar 2022 11:33:44 -0800 (PST)
In-Reply-To: <d58000c6-a6fc-489e-8633-934083558a93n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2600:1700:291:29f0:68b9:546f:8e1c:46cb;
posting-account=H_G_JQkAAADS6onOMb-dqvUozKse7mcM
NNTP-Posting-Host: 2600:1700:291:29f0:68b9:546f:8e1c:46cb
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com>
<nLf*530Hy@news.chiark.greenend.org.uk> <605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com>
<ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com> <svjpo5$qta$1@dont-email.me>
<05ff4f22-0ae7-471f-b5e8-afaf294bde90n@googlegroups.com> <2022Mar1.114449@mips.complang.tuwien.ac.at>
<svlj1h$rp5$1@dont-email.me> <1bff1203-ff18-4a89-ad13-76f587f24cd9n@googlegroups.com>
<d58000c6-a6fc-489e-8633-934083558a93n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <2d314f4b-7f8b-4382-9cfa-a96881769fe9n@googlegroups.com>
Subject: Re: Sequential Consistency
From: MitchAl...@aol.com (MitchAlsup)
Injection-Date: Tue, 01 Mar 2022 19:33:44 +0000
Content-Type: text/plain; charset="UTF-8"
Lines: 55
 by: MitchAlsup - Tue, 1 Mar 2022 19:33 UTC

On Tuesday, March 1, 2022 at 1:22:06 PM UTC-6, Quadibloc wrote:
> On Tuesday, March 1, 2022 at 11:33:20 AM UTC-7, MitchAlsup wrote:
>
> > You already don't get result delivery in instruction order in pipelined
> > FPUs, consider FADD versus FDIV.
>
> > On the other hand, HW goes through lots of hassle to provide precise
> > exceptions................all to give the illusion of a single point of control.
> To me, that asks the question: can we do without the illusion of a
> single point of control?
>
> Some instruction sets had branch instructions that didn't branch until
> after the following instruction or two was executed. So I guess you could
> have a divide instruction that had delay slots too.
>
> Precise exceptions were desired so that if something went wrong in
> a program, it was known where it went wrong, so that an interrupt
> routine could presumably fix it. This could be done without a pipelined
> computer pretending not to be pipelined, the interrupt would just have,
> instead of a return address, a lengthy discription of where everything
> happened to be in flight when the exception occurred.
>
> Of course, there are _good_ reasons why that hasn't even been tried.
<
Mc88100 had imprecise exceptions. You would take an exception and
SW would unload the machine often getting 3-4-5 exceptions pending
on the excepted thread. DG Unix port was configured to push each
exception into the user state as a signal, and upon return, push the
next one.
<
The problem was that application programmers had been given the
illusion that there could only be ONE exception at a time, and then
used the longjump() to go back to where they wanted to be rather
than let the OS push the exceptions and let the user handle them.
<
The applications which let the OS push each exception into their handlers
and not longjump() to safety worked perfectly.
<
A) so it has been tried
B) It worked just fine
C) old software made assumptions that were never valid
D) it was cheaper to fix HW than to fix SW.
>
> But in a way, this seems to me to be a pointless discussion. Of course
> we could say that out-of-order execution is wicked, and instead we
> should have a larger number of in-order cores for the same throughput
> without these issues and wasted transistors.
<
Notice that the most recent IBM mainframes has 12 Fetch-Decode
stages and 15 Write-Retire stages.
>
> But because we don't have the magic solution for parallel programming,
> and probably never will, the cost for that is higher latency. Sometimes,
> even if not as often as people seem to think, that matters.
>
> John Savard

Re: Sequential Consistency

<pLf*o15Hy@news.chiark.greenend.org.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=23860&group=comp.arch#23860

 copy link   Newsgroups: comp.arch
Path: i2pn2.org!i2pn.org!news.niel.me!nntp.terraraq.uk!nntp-feed.chiark.greenend.org.uk!ewrotcd!.POSTED!not-for-mail
From: theom+n...@chiark.greenend.org.uk (Theo Markettos)
Newsgroups: comp.arch
Subject: Re: Sequential Consistency
Date: 01 Mar 2022 19:34:19 +0000 (GMT)
Organization: University of Cambridge, England
Lines: 42
Message-ID: <pLf*o15Hy@news.chiark.greenend.org.uk>
References: <e32018d2-2a73-4aa4-a881-b193600719d6n@googlegroups.com> <nLf*530Hy@news.chiark.greenend.org.uk> <605c5121-3a00-4570-b3af-d3a8c6c7c66cn@googlegroups.com> <ad2ec901-02b5-4a98-a548-24e325027cd1n@googlegroups.com>
NNTP-Posting-Host: chiark.greenend.org.uk
X-Trace: chiark.greenend.org.uk 1646163261 30171 212.13.197.229 (1 Mar 2022 19:34:21 GMT)
X-Complaints-To: abuse@chiark.greenend.org.uk
NNTP-Posting-Date: Tue, 1 Mar 2022 19:34:21 +0000 (UTC)
User-Agent: tin/1.8.3-20070201 ("Scotasay") (UNIX) (Linux/3.16.0-11-amd64 (x86_64))
Originator: theom@chiark.greenend.org.uk ([212.13.197.229])
 by: Theo Markettos - Tue, 1 Mar 2022 19:34 UTC

MitchAlsup <MitchAlsup@aol.com> wrote:
> So, PCIe supports sequential consistency on a per Bus: device, function,
> but not between Busses: devices, functions level ?!?
> <
> A series of writes to one device arrive at device in order, but two or more
> series of writes to differing devices arrive at each device in order, but
> may arrive at one device out of order with respect to sending order.

Essentially yes. See table 2-24 on page 101:
https://www.cl.cam.ac.uk/~djm202/pdf/specifications/pcie/PCI_Express_Base_Rev_2.0_20Dec06a.pdf

Writes can't reorder, and reads can't pass writes, but writes can pass reads
in some circumstances. The timing of the read response (completion) is
considered separately from the issuing of the read request.

There's no guarantees between devices, in particular since PCIe is not a
point to point interconnect: there may be multiple CPUs and switches in the
path.

Additionally this guarantee is *only* at the level of MMIO reads and writes
(and DMA reads/writes going the other way). The higher level concepts like
queues or ring buffers etc have no guarantees provide by this, unless such
have been separately built into their design.

> <
> CPU[c] performs start I/O to 3 devices, by issuing a series of MMI/O
> write requests, first to device[1] in its entirety, then to device[2] in its
> entirely, then to device[3] in its entirety.
> <
> However due to retransmission, and bridges; the series of writes
> arrive at devices in the order device[3] before device[2] before
> device[3].
> <
> Is this still within sequential consistency ?

PCIe doesn't call this sequential consistency. You can presumably define it
to be so if you want, but I'm not sure what that definition would be useful
for.

(more plausibly, some other synchronisation mechanism would be used)

Theo

1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor