Litmus Test 7 Impossible Sequence | Compaq ECQD2KCTE specification

There is V2 ⇐ U1 ⇐ U2 ⇐ U3 ⇐ V1. There are no conflicts in this sequence. There are no violations of the definition of BEFORE.

In litmus tests 4, 5, and 6, writes to two different locations x and y are observed (by another processor) to occur in the opposite order than that in which they were performed. An update to y propagates quickly to Pj, but the update to x is delayed, and Pi and Pj do not both have MBs.

5.6.2.7 Litmus Test 7 (Impossible Sequence)

Initially, locations x and y contain 1:

Pi

Pj

[U1]Pi:W<8>(x,2)[V1]Pj:R<8>(y,2)

[U2]Pi:MB[V2]Pj:MB

[U3]Pi:W<8>(y,2)[V3]Pj:R<8>(x,1)

Analysis:

<1>	V3 reading 1 implies V3 ⇐ U1, by storage and visibility.
<2>	V1 reading 2 implies U3 ⇐ V1, by storage and visibility.
<3>	U1 ⇐ U2 ⇐ U3, by processor issue constraints.
<4>	V1 ⇐ V2 ⇐ V3, by processor issue constraints.
<5>	By <2>, <3>, and <4>, U1 ⇐ U2 ⇐ U3 ⇐ V1 ⇐ V2 ⇐ V3.

Both <1> and <5> cannot be true, so if V1 reads 2, then V3 must also read 2.

If both x and y are in memory-like regions, the sequence remains impossible if U2 is changed to a WMB. Similarly, if both x and y are in non-memory-like regions, the sequence remains impossible if U2 is changed to a WMB.

5.6.2.8 Litmus Test 8 (Impossible Sequence)

Initially, locations x and y contain 1:

Pi

Pj

[U1]Pi:W<8>(x,2)[V1]Pj:W<8>(y,2)

[U2]Pi:MB[V2]Pj:MB

[U3]Pi:R<8>(y,1)[V3]Pj:R<8>(x,1)

Analysis:

<1>	V3 reading 1 implies V3 ⇐ U1, by storage and visibility.
<2>	U3 reading 1 implies U3 ⇐ V1, by storage and visibility.
<3>	U1 ⇐ U2 ⇐ U3, by processor issue constraints.
<4>	V1 ⇐ V2 ⇐ V3, by processor issue constraints.
<5>	By <2>, <3>, and <4>, U1 ⇐ U2 ⇐ U3 ⇐ V1 ⇐ V2 ⇐ V3.

Both <1> and <5> cannot be true, so if U3 reads 1, then V3 must read 2, and vice versa.

5–20Alpha Architecture Handbook

Image 232

Compaq ECQD2KCTE manual Litmus Test 7 Impossible Sequence, Litmus Test 8 Impossible Sequence

Contents

Alpha Architecture Handbook October Table of Contents Instruction Formats Page 10.19 Integer Register to Floating-Point Register Move System Architecture and Programming Implications Digital Unix Ieee Floating-Point Conformance Index Figures Tables Xiii Xiv Preface Page Chapter Alpha Approach to Risc ArchitectureAlpha Is a True 64-Bit Architecture Alpha Is Designed for Very High-Speed Implementations Alpha Approach to Byte Manipulation Alpha Approach to Multiprocessor Shared MemoryAlpha Instructions Include Hints for Achieving Higher Speed PALcode Alpha’s Very Flexible Privileged Software Library Data Format Overview Alpha and Programming Languages Instruction Overview Instruction Format OverviewPALcode Instructions Load/Store Instructions Branch InstructionsInteger Operate Instructions Terminology and Conventions Instruction Set CharacteristicsFloating-Point Operate Instructions Security Holes NumberingUnpredictable and Undefined Aligned and Unaligned Ranges and ExtentsUnaligned Must Be Zero MBZ Read As Zero RAZShould Be Zero SBZ Ignore IGNPage Addressing Data TypesByte Word Longword Quadword VAX Floating-Point Formats Ffloating Ffloating Load Exponent Mapping Mapf Gfloating Gfloating Register Format Dfloating Ieee Floating-Point Formats SFloating Sfloating Load Exponent Mapping Maps Memory Register Tfloating 13 Tfloating Datum 14 Tfloating Register Format XFloating 15 Xfloating Datum XFloating Big-Endian Formats Longword Integer Format in Floating-Point Unit 17 Xfloating Big-Endian Datum Quadword Integer Format in Floating-Point Unit Data Types with No Hardware Support Big-Endian Addressing Support 23 Little-Endian Byte Addressing 14Alpha Architecture Handbook Alpha Registers Program CounterInteger Registers Implementation note Floating-Point Registers Lock Registers Notation Processor Cycle Counter PCC RegisterOptional Registers Memory Prefetch Registers Operand Notation Operand Notation MeaningOperand Value Notation Meaning Expression Operand Notation Meaning Operand Access Type Notation Operand Access Type Notation MeaningInstruction Operand Notation Operand Name Notation Operators Operand Data Type NotationOperand Data Type Notation Meaning Operators Meaning Bit concatenation DIV CaseLoadlocked Not PhysicaladdressPriorityencode LTU Instruction Formats Notation ConventionsSoftware Note XOR Memory Instruction Format Memory Format Instructions with a Function Code Operate Instruction Format Branch Instruction FormatMemory Format Jump Instructions Floating-Point Operate Instruction Format Floating-Point Operate Instruction Format Floating-Point Convert Instructions PALcode Instruction FormatFloating-Point/Integer Register Moves PALcode Instruction Format Page Instruction Set Overview Instruction Type Section Subsetting Rules Floating-Point Subsets Opcode Qualifiers Software Emulation RulesOpcode Qualifiers Meaning Memory Integer Load/Store Instructions Memory Integer Load/Store Instructions Mnemonic Operation Load Address Load Memory Data into Integer Register LDL Implementation Notes Load Unaligned Memory Data into Integer Register Load Memory Data into Integer Register Locked 10Alpha Architecture Handbook Implementation Notes Store Integer Register Data into Memory Conditional Stqc BEQ Hardware/Software Implementation Note Store Integer Register Data into Memory 16Alpha Architecture Handbook Store Unaligned Integer Register Data into Memory Control Instructions Control Instructions Summary Mnemonic Operation BNE BSRJMP JSR Conditional Branch Unconditional Branch Jumps Encoding Meaning Count instruction CIX extension implementation note Integer Arithmetic InstructionsInteger Arithmetic Instructions Summary Mnemonic Operation Longword Add Addl S4ADDL Scaled Longword AddS8ADDL Quadword Add Addq S4ADDQ Scaled Quadword AddS8ADDQ Integer Signed Compare Integer Unsigned Compare Count Leading Zero Count Population Count Trailing Zero Longword Multiply Mull Quadword Multiply Mulq Unsigned Quadword Multiply High Longword Subtract Subl S4SUBL Scaled Longword SubtractS8SUBL Quadword Subtract Subq S4SUBQ Scaled Quadword SubtractS8SUBQ Logical and Shift Instructions Logical and Shift Instructions Summary Mnemonic Operation Logical Functions Conditional Move Integer Is exactly equivalent to Shift Logical Shift Arithmetic Byte Manipulation Instructions Instruction Meaning Described in Section Inswh InslhInsqh Mskbl Compare Byte BEQ Loop To compare two character strings for greater/equal/less Extract Byte Ldqu Optimized examples Big-endian examples Byte Insert 56Alpha Architecture Handbook Byte Mask Insqh Inswh Sign Extend Zero Bytes Floating-Point Instructions Subsets and FaultsSingle-Precision Operations Definitions Alpha finite number Denormal Dirty zeroInfinity Non-finite number Encodings True zeroSign Exponent Fraction Vax Meaning Finite VAX Rounding Modes Rounding ModesIeee Rounding Modes VAX Rounding Mode Instruction Notation Ieee Rounding Mode Instruction NotationComputational Models VAX-Format Arithmetic with Precise Exceptions IEEE-Compliant Arithmetic High-Performance VAX-Format ArithmeticIEEE-Compliant Arithmetic Without Inexact Exception High-Performance IEEE-Format Arithmetic Trapping ModesVAX Trapping Modes When /U or /V mode is specified VAX Trapping Modes Summary Trap Mode Notation Meaning Ieee Trapping Modes Summary of Ieee Trapping Modes Trap Mode Notation Meaning SUI Arithmetic Trap Completion SVI Trap Shadow Length Rules Page Invalid Operation INV Arithmetic Trap Division by Zero DZE Arithmetic Trap Overflow OVF Arithmetic Trap Ieee Floating-Point Trap Disable Bits Underflow UNF Arithmetic TrapInexact Result INE Arithmetic Trap Integer Overflow IOV Arithmetic Trap Floating-Point Control Register Fpcr Ieee Denormal Control Bits Ieee Rounding Mode Selected Floating-Point Control Register Fpcr FormatPage Accessing the Fpcr Saving and Restoring the Fpcr Default Values of the FpcrSoftware Notes Floating-Point Instruction Function Field Format Floating-Point Instruction Function Field Contents Meaning for Opcodes 1616 ITOFS/ITOFT FNCSQRTS/SQRTT Unpredictable Ieee Standard Conversion of NaN and Infinity Values Generating NaN Values Copying NaN ValuesPropagating NaN Values Memory Format Floating-Point Instructions Load Ffloating Load Gfloating Load Sfloating Load Tfloating Store Ffloating Store Gfloating Store Sfloating Store Tfloating Branch Format Floating-Point Instructions FBxx Fa.rq,disp.al Branch format Page Floating-Point Operate Format Instructions Addf AddgAdds Ieee Mulf MulgMuls Mult Copy Sign Convert Integer to Integer Floating-Point Conditional Move Fcmovne F3,F2,F1 Move from/to Floating-Point Control Register VAX Floating Add Ieee Floating Add VAX Floating Compare CmpgeqCmpgle Cmpglt Ieee Floating Compare CmpteqCmptle Cmptlt Convert VAX Floating to Integer Convert Integer to VAX Floating Convert VAX Floating to VAX Floating Convert Ieee Floating to Integer Convert Integer to Ieee Floating Convert Ieee SFloating to Ieee TFloating Convert Ieee TFloating to Ieee SFloating VAX Floating Divide Ieee Floating Divide Floating-Point Register to Integer Register Move Integer Register to Floating-Point Register Move Itofs is exactly equivalent to the sequence VAX Floating Multiply Ieee Floating Multiply VAX Floating Square Root Ieee Floating Square Root VAX Floating Subtract Ieee Floating Subtract Miscellaneous Instructions 17 Miscellaneous Instructions Summary Mnemonic Operation Architecture Mask 134Alpha Architecture Handbook Call Privileged Architecture Library Evict Data Cache Block Implementation Note Exception Barrier Prefetch Data 140Alpha Architecture Handbook Implementation Version Memory Barrier Read Processor Cycle Counter Trap Barrier Write Hint Implementation Note Write Memory Barrier Processor Processor j VAX Compatibility Instructions 18 VAX Compatibility Instructions Summary Mnemonic Operation VAX Compatibility Instructions Multimedia Graphics and Video Support Mnemonic Operation Byte and Word Minimum and Maximum Instruction mnemonics Pixel Error Pack Bytes Unpack Bytes Coherency of Memory Access Physical Address Space CharacteristicsIntroduction Granularity of Memory Access Software/Hardware Note Width of Memory Access Memory-Like and Non-Memory-Like Behavior Caches and Write Buffers Translation Buffers and Virtual CachesHardware/Software Coordination Note Page Data Sharing Atomic Update of a Single DatumAtomic Change of a Single Datum Atomic Update of Data Structures STQ 8Alpha Architecture Handbook Ordering Considerations for Shared Data Structures Read/Write Ordering Alpha Shared Memory Model Implementation Note Definition of Processor Issue Constraints Architectural Definition of Processor Issue SequenceDefinition of Before and After Processor Issue Constraints 1st↓ 2nd → PiIn=4y,b PiRny,b PiWny,b PiMB PiIMB Definition of Visibility Definition of Location Access ConstraintsDefinition of Storage Definition of Dependence Constraint Definition of Load-Locked and Store-Conditional Litmus Tests TimelinessLitmus Test 1 Impossible Sequence PiPj Litmus Test 2 Impossible Sequence Litmus Test 3 Impossible Sequence Litmus Test 5 Sequence Okay Litmus Test 4 Sequence OkayLitmus Test 6 Sequence Okay Litmus Test 7 Impossible Sequence Litmus Test 8 Impossible Sequence Litmus Test 10 Sequence Okay Litmus Test 9 Impossible SequenceLitmus Test 11 Impossible Sequence Implied Barriers Implications for SoftwareSingle Processor Data Stream Single Processor Instruction Stream See Footnote 1 on Multiprocessor Context Switch First Processor Second ProcessorPage Multiprocessor Send/Receive Interrupt Implications for Memory Mapped I/O Multiple Processors Writing to a Single I/O Device Implications for Hardware Arithmetic Traps Dictable PALcode PALcode Instructions and Functions PALcode Environment Special Functions Required for PALcode PALcode Replacement PALcode Effects on System Code Required PALcode Instructions PALcode Instructions that Require Recognition Mnemonic Name Required PALcode Instructions Mnemonic Type Operation DrainaHalt IMB Drain Aborts Callpal Draina Halt Callpal Halt Instruction Memory Barrier Callpal IMB Console Subsystem Overview Page Input/Output Overview Page OpenVMS Alpha Unprivileged OpenVMS Alpha PALcode Chme ChmkChms Chmu Insqhil InsqhilrInsqhiq Insqhiqr Insqtilr InsqtiqInsqtiqr Insquel Rdps ReadunqREI Remqhil Remqhiqr RemqtilRemqtilr Remqtiq Remquel RemqueqRscc Swasten Privileged OpenVMS Alpha Palcode CflushLdqp Mfpr Swpctx StqpWtint Page Unprivileged Digital Unix PALcode Mnemonic Operation and Description Privileged Digital Unix PALcode 10-3 10-4Alpha Architecture Handbook Unprivileged Windows NT Alpha PALcode Unprivileged Windows NT Alpha PALcode Instruction Summary Privileged Windows NT Alpha PALcode 11-3 11-4Alpha Architecture Handbook 11-5 Page Appendix a Hardware-Software Compact Instruction Alignment Instruction-Stream ConsiderationsBranch Prediction and Minimizing Branch-Taken Factor Figure A-1 Branch-Format BSR and BR Opcodes Data-Stream Considerations Improving I-Stream Density FactorInstruction Scheduling Factor Data Alignment Factor Shared Data in Multiple Processors Factor Avoiding Cache/TB Conflicts Factor Figure A-3 Bad Allocation in Cache Sequential Read/Write Factor Prefetching Factor Aligned Byte/Word Within Register Memory Accesses Code Sequences Division Stylized Code Forms Byte Swap4.1 NOP Clear a Register Load Literal Register-to-Register Move Negate4.6 not Booleans Exceptions and Trap Barriers Pseudo-Operations Stylized Code Forms Software Considerations A-15 Timing Considerations Atomic Sequences Appendix B Alpha Choices for Ieee Options 2Alpha Architecture Handbook Alpha Support for OS Completion Handlers Ieee Floating-Point Control FPC Quadword Figure B-1 Ieee Floating-Point Control FPC QuadwordPage Mapping to Ieee Standard Figure B-2 Ieee Trap Handling Behavior Completion Signal Alpha Instructions Code Handler Table B-2 Ieee Floating-Point Trap Handling User Hardware1 MULx Output Exceptions CVTff Output Exceptions Cmptlt Cmptle Input Exceptions SQRTx Output Exceptions Division by Zero OverflowUnderflow Inexact Appendix C Common Architecture Instruction Summary ADDL/V Table C-2 Common Architecture InstructionsADDQ/V 15.0AF Convert Gfloating to quadword MULL/V MULQ/V SUBL/V SUBQ/V Ieee Floating-Point Instructions Table C-3 Ieee Floating-Point Instruction Function Codes VAX Floating-Point Instructions Programming Note Independent Floating-Point Instructions Opcode Summary Table C-7 Key to Opcode Summary Symbol Meaning Table C-6 Opcode Summary Common Architecture Opcodes in Numerical Order Table C-8 Common Architecture Opcodes in Numerical Order Instruction Summary C-11 Addt Instruction Summary C-13 OpenVMS Alpha PALcode Instruction Summary Mfprasn MfprespMfprfen Mfpripl Table C-12 Digital Unix Privileged PALcode Instructions Digital Unix PALcode Instruction SummaryMnemonic Opcode Description Windows NT Alpha Instruction Summary Table C-14 Windows NT Alpha Privileged PALcode instructions PALcode Opcodes in Numerical Order Table C-15 PALcode Opcodes in Numerical OrderWindows NT OpenVMS Alpha Wtint 00.003F 00.0063 Required PALcode Opcodes Opcodes Reserved to PALcodeTable C-16 Required PALcode Opcodes Mnemonic Type Table C-17 Opcodes Reserved for PALcode Mnemonic Opcodes Reserved to Compaq Unused Function Code BehaviorTable C-18 Opcodes Reserved for Compaq Mnemonic OPC01 OPC02 OPC03 OPC04 OPC05 OPC06 OPC07 Ascii Character Set Table C-19 Ascii Character Set Hex Code Appendix D Processor Type AssignmentsTable D-1 Processor Type Assignments Major Type Minor Type EV3 PALcode Variation Assignments Architecture Mask and Implementation Values Table D-3 Amask Bit Assignments Bit MeaningTable D-4 Implver Value Assignments Meaning Digital UnixPage Appendix E Waivers DECchip 21264 LDxL/STxC with WH64 Violation Implementation-Specific Functionality DECchip 21064/21066/21068 Performance Monitoring For the OpenVMS Alpha Operating System Disable performance monitoring Functions and Arguments for the DECchip 21064/21066/21068 Select desired events muxctl Select performance monitoring options= PCMUX0 = PCMUX1 Value Description PC0 PC1 DECchip 21164/21164PC Performance Monitoring Performance Monitor Interrupt Mechanism Input Contents Register Bits Meaning Windows NT Alpha Functions and Argument CTR1 CTR0PCSEL0 OpenVMS Alpha and Digital Unix Functions and Arguments ModeselectPCSEL1 PCSEL2 Disable performance monitoring do not reset counters Select desired events Muxselect Select interrupt frequencies Read the counters Operate on counter MBZ MBZ PCSEL0MBZ PCSEL1 Bits Meaning Counters Operate Under These Modes When Bits SetS U P 6310 Table E-13 21164/21164PC Counter 1 PCSEL1 Event Selection Table E-14 21164/21164PC Counter 2 PCSEL2 Event Selection Value Meaning Table E-15 21164 CBOX1 Event SelectionTable E-16 21164 CBOX2 Event Selection Table E-17 21164PC PM0MUX Event Selection Table E-18 21164PC PM1MUX Event Selection 3 21264 Performance Monitoring SEXTPCTR0CTL47 PCTR0IERCMPCEN0 PCTR1 SL1 Bit value Meaning Select logging options Enable and write selected counters R17/a1 Bits Meaning Table E-26 21264 Enable and Write Counters for OpenVMS Alpha Page Index Index-2 Index-3 Index-4 Index-5 Index-6 Index-7 Index-8 Index-9 Index-10 Index-11 Index-12 Index-13