From owner-sc22wg5+sc22wg5-dom8=www.open-std.org@open-std.org Tue Jul 30 22:11:02 2019 Return-Path: X-Original-To: sc22wg5-dom8 Delivered-To: sc22wg5-dom8@www.open-std.org Received: by www.open-std.org (Postfix, from userid 521) id 51445358A01; Tue, 30 Jul 2019 22:11:02 +0200 (CEST) Delivered-To: sc22wg5@open-std.org Received: from ppa02.jpl.nasa.gov (ppa02.jpl.nasa.gov [128.149.137.113]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by www.open-std.org (Postfix) with ESMTP id C3D5C356961 for ; Tue, 30 Jul 2019 22:10:58 +0200 (CEST) Received: from pps.filterd (ppa02.jpl.nasa.gov [127.0.0.1]) by ppa02.jpl.nasa.gov (8.16.0.27/8.16.0.27) with SMTP id x6UKAFfT078581 for ; Tue, 30 Jul 2019 13:10:56 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=jpl.nasa.gov; h=subject : from : reply-to : to : content-type : date : message-id : mime-version; s=InSight1906; bh=aDX3x3hd2yoNhgQWzwcToM9MNahvKPWCEH070iW1C2A=; b=1Ga+oYgP4rMuh9E9KXKLRTa4deoAPhr/ByiwM4MZYouGQcUXtDoz4oWk3f8qbXAMgLdj T/30j5gX+2MKxC4iKg5awJDIt1/Jacj6eVzBkd7gmi7t87Dsx0OHc4TcOm0lXiLf0fvo lmTD+uE8AdBbnz3gek/aBueIShQZ+fXmqp1L+pkakVldctD+gNRDxGjcadc7pXJOWuWI IocXa6hbRjbd5tUkl4LkHvGVf6AxL3yJpb0ABxhf7vzL4GWvLNWW0j1ucPmQsGxXGdx8 YyBV/jLq1HM10QyCSbbSjUWdkn6Ri3hDXk6DNexzZXOPjjR3vpZvBODPeM+FVuyQEmSU tw== Received: from mail.jpl.nasa.gov (altphysenclup01.jpl.nasa.gov [128.149.137.52]) by ppa02.jpl.nasa.gov with ESMTP id 2u27pru9ry-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT) for ; Tue, 30 Jul 2019 13:10:56 -0700 Received: from [137.79.7.57] (math.jpl.nasa.gov [137.79.7.57]) by smtp.jpl.nasa.gov (Sentrion-MTA-4.3.1/Sentrion-MTA-4.3.1) with ESMTP id x6UKAs7f028505 (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128 bits) verified NO) for ; Tue, 30 Jul 2019 13:10:55 -0700 Subject: Follow up on dot product request From: Van Snyder Reply-To: Van.Snyder@jpl.nasa.gov To: sc22wg5 Content-Type: multipart/alternative; boundary="=-b9hPn76Qjqua6zS4rIXk" Organization: Yes Date: Tue, 30 Jul 2019 13:10:53 -0700 Message-ID: <1564517454.31099.232.camel@math.jpl.nasa.gov> Mime-Version: 1.0 X-Mailer: Evolution 2.32.3 (2.32.3-37.el6) X-Source-IP: math.jpl.nasa.gov [137.79.7.57] X-Source-Sender: Van.Snyder@jpl.nasa.gov X-AUTH: Authorized X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:,, definitions=2019-07-30_10:,, signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 priorityscore=1501 malwarescore=0 suspectscore=0 phishscore=0 bulkscore=0 spamscore=0 clxscore=1015 lowpriorityscore=0 mlxscore=0 impostorscore=0 mlxlogscore=433 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1906280000 definitions=main-1907300205 Sender: owner-sc22wg5@open-std.org Precedence: bulk --=-b9hPn76Qjqua6zS4rIXk Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 7bit From Ulrich Kulisch, concerning a correctly-rounded dot product: Primarily, we should react as mathematicians and not as IEEE 754 enthusiasts. The 4,266 bits solely are a consequence of the IEEE 754 standard. Do we really need an exponent range of 308? The old /370 architecture provided an exponent range of about 75 and most problems (I would say 98 %) could conveniently be solved within this exponent range. For this exponent range the long accumulator shrinks to about 1,100 bits. So if we provide an accumulator of this size about 98% of the cases would run on fast hardware. If overflow occurs, the calculation could be repeated with a software algorithm. "The importance of the EDP [Exact Dot Product] for high speed verified computing has not been well understood by the scientific computing community for quite some time. So I mention it here briefly. A guaranteed solution of a system of linear equations can be obtained in two steps. The first step computes an approximate solution by some kind of Gaussian elimination in conventional floating-point arithmetic. The second step, the verification step, then computes a highly accurate guaranteed enclosure of the solution. By an early estimate of Rump [6], the verification step can be done with less than 6 times the number of elementary floating-point operations needed for computing an approximation in the first step. The verification step just consists of dot products. Hardware implementations of the EDP at Karlsruhe in 1993 [3, 4] and at Berkeley in 2013 [5] show that it can be computed in about one-sixth of the time needed for computing a possibly wrong result in conventional floating-point arithmetic. So, the EDP reduces the time needed for the verification step to about the time needed for computing an approximate solution by Gaussian elimination. This is a tremendous gain in computing speed. In other words, a verified solution of a system of linear equations can be computed in about twice the time needed for computing an approximate solution by some kind of Gaussian elimination." Of course, refinement of the solution of a linear system is not the only application of a dot product. There are numerous other problems wherein a poorly-conditioned dot product leads to incurrect results. A poorly-conditioned dot product is just a special case of a poorly-conditioned sum. So 19-184 should be amended to request a correctly rounded SUM as well. --=-b9hPn76Qjqua6zS4rIXk Content-Type: text/html; charset="utf-8" Content-Transfer-Encoding: quoted-printable =46rom Ulrich Kulisch, concerning a correctly-rounded dot product:

Primarily, we should react as mathematicians and not as IEEE 754 enthus= iasts. The 4,266 bits solely are a consequence of the IEEE 754 standard. Do= we really need an exponent range of 308? The old /370 architecture provide= d an exponent range of about 75 and most problems (I would say 98 %) could = conveniently be solved within this exponent range. For this exponent range = the long accumulator shrinks to about 1,100 bits.

So if we provide an accumulator of this size about 98% of the cases wou= ld run on fast hardware. If overflow occurs, the calculation could be repea= ted with a software algorithm.

"The importance of the EDP [Exact Dot Product] for high speed veri= fied computing has not been well understood by the scientific computing com= munity for quite some time. So I mention it here briefly. A guaranteed solu= tion of a system of linear equations can be obtained in two steps. The firs= t step computes an approximate solution by some kind of Gaussian eliminatio= n in conventional floating-point arithmetic. The second step, the verificat= ion step, then computes a highly accurate guaranteed enclosure of the solut= ion. By an early estimate of Rump [6], the verification step can be done wi= th less than 6 times the number of elementary floating-point operations nee= ded for computing an approximation in the first step. The verification step= just consists of dot products. Hardware implementations of the EDP at Karl= sruhe in 1993 [3, 4] and at Berkeley in 2013 [5] show that it can be comput= ed in about one-sixth of the time needed for computing a possibly wrong res= ult in conventional floating-point arithmetic. So, the EDP reduces the time= needed for the verification step to about the time needed for computing an= approximate solution by Gaussian elimination. This is a tremendous gain in= computing speed. In other words, a verified solution of a system of linear= equations can be computed in about twice the time needed for computing an = approximate solution by some kind of Gaussian elimination."

Of course, refinement of the solution of a linear system is not the only ap= plication of a dot product.  There are numerous other problems wherein= a poorly-conditioned dot product leads to incurrect results.

A poorly-conditioned dot product is just a special case of a poorly-conditi= oned sum.  So 19-184 should be amended to request a correctly rounded = SUM as well.


--=-b9hPn76Qjqua6zS4rIXk--