Manuals / Compaq / Computer Equipment / Laptop

Compaq ECQD2KCTE manual Atomic Update of Data Structures, Stq

Models: ECQD2KCTE

1 371

Download 371 pages 20.35 Kb

Page 219

This load-locked/store-conditional paradigm may be used whenever an atomic update of a shared aligned quadword is desired, including getting the effect of atomic byte writes.

5.5.3 Atomic Update of Data Structures

Before accessing shared writable data structures (those that are not a single aligned longword or quadword), the programmer can acquire control of the data structure by using an atomic update to set a software lock variable. Such a software lock can be cleared with an ordinary store instruction.

A software-critical section, therefore, may look like the sequence:

stq_c_loop:
spin_loop:
LDQ	R1,lock_variable	; This optional spin-loop code
BLBS R1,already_set		; should be used unless the
		; lock is known to be low-contention.
LDQ_L R1,lock_variable		; \
BLBS R1,already_set		;	\
OR	R1,#1,R2	;	> Set lock bit
STQ_C R2,lock_variable		;	/
BEQ	R2,stq_c_fail	; /

MB

<critical section: updates various data structures>

MB		; Second MB
STQ	R31,lock_variable	; Clear lock bit
:
:
already_set:
<code to block or reschedule or test for too many iterations>
BR	spin_loop
stq_c_fail:
<code to test for too many iterations>
BR	stq_c_loop

This code has a number of subtleties:

•If the lock_variable is already set, the spin loop is done without doing any stores. This avoidance of stores improves memory subsystem performance and avoids the deadlock described below. The loop uses an ordinary load. This code sequence is preferred unless the lock is known to be low-contention, because the sequence increases the probability that the LDQ_L hits in the cache and the LDQ_L/STQ_C sequence complete quickly and successfully.

•If the lock_variable is actually being changed from 0 to 1, and the STQ_C fails (due to an interrupt, or because another processor simultaneously changed lock_variable), the entire process starts over by reading the lock_variable again.

•Only the fall-through path of the BLBS instructions does a STx_C; some implementa- tions may not allow a successful STx_C after a branch-taken.

•Only register-to-register operate instructions are used to do the modify.

System Architecture and Programming Implications 5–7

Image 219

Compaq ECQD2KCTE manual Atomic Update of Data Structures, Stq

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 Alpha Is Designed for Very High-Speed Implementations ChapterAlpha Approach to Risc Architecture Alpha Is a True 64-Bit ArchitecturePALcode Alpha’s Very Flexible Privileged Software Library Alpha Approach to Byte ManipulationAlpha Approach to Multiprocessor Shared Memory Alpha Instructions Include Hints for Achieving Higher SpeedAlpha and Programming Languages Data Format OverviewInstruction Format Overview Instruction OverviewPALcode Instructions Branch Instructions Load/Store InstructionsInteger Operate Instructions Instruction Set Characteristics Terminology and ConventionsFloating-Point Operate Instructions Numbering Security HolesUnpredictable and Undefined Ranges and Extents Aligned and UnalignedUnaligned Ignore IGN Must Be Zero MBZRead As Zero RAZ Should Be Zero SBZPage Word AddressingData Types ByteQuadword LongwordFfloating VAX Floating-Point FormatsGfloating Ffloating Load Exponent Mapping MapfDfloating Gfloating Register FormatIeee Floating-Point Formats Sfloating Load Exponent Mapping Maps Memory Register SFloating13 Tfloating Datum TfloatingXFloating 14 Tfloating Register FormatXFloating Big-Endian Formats 15 Xfloating Datum17 Xfloating Big-Endian Datum Longword Integer Format in Floating-Point UnitData Types with No Hardware Support Quadword Integer Format in Floating-Point Unit23 Little-Endian Byte Addressing Big-Endian Addressing Support14Alpha Architecture Handbook Implementation note Alpha RegistersProgram Counter Integer RegistersLock Registers Floating-Point RegistersMemory Prefetch Registers NotationProcessor Cycle Counter PCC Register Optional RegistersExpression Operand Notation Meaning Operand NotationOperand Notation Meaning Operand Value Notation MeaningOperand Name Notation Operand Access Type NotationOperand Access Type Notation Meaning Instruction Operand NotationOperators Meaning OperatorsOperand Data Type Notation Operand Data Type Notation MeaningBit concatenation Case DIVLoadlocked LTU NotPhysicaladdress PriorityencodeXOR Instruction FormatsNotation Conventions Software NoteMemory Format Instructions with a Function Code Memory Instruction FormatBranch Instruction Format Operate Instruction FormatMemory Format Jump Instructions Floating-Point Operate Instruction Format Floating-Point Operate Instruction FormatPALcode Instruction Format Floating-Point Convert InstructionsFloating-Point/Integer Register Moves PALcode Instruction Format Page Instruction Type Section Instruction Set OverviewFloating-Point Subsets Subsetting RulesSoftware Emulation Rules Opcode QualifiersOpcode Qualifiers Meaning Memory Integer Load/Store Instructions Mnemonic Operation Memory Integer Load/Store InstructionsLoad Address LDL Load Memory Data into Integer RegisterImplementation 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 Summary Mnemonic Operation Control InstructionsJSR BNEBSR JMPConditional Branch Unconditional Branch Jumps Encoding Meaning Integer Arithmetic Instructions Count instruction CIX extension implementation noteInteger Arithmetic Instructions Summary Mnemonic Operation Addl Longword AddScaled Longword Add S4ADDLS8ADDL Addq Quadword AddScaled Quadword Add S4ADDQS8ADDQ Integer Signed Compare Integer Unsigned Compare Count Leading Zero Count Population Count Trailing Zero Mull Longword MultiplyMulq Quadword MultiplyUnsigned Quadword Multiply High Subl Longword SubtractScaled Longword Subtract S4SUBLS8SUBL Subq Quadword SubtractScaled Quadword Subtract S4SUBQS8SUBQ Logical and Shift Instructions Summary Mnemonic Operation Logical and Shift InstructionsLogical Functions Conditional Move Integer Is exactly equivalent to Shift Logical Shift Arithmetic Instruction Meaning Described in Section Byte Manipulation InstructionsMskbl InswhInslh InsqhBEQ Loop Compare ByteTo 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 Subsets and Faults Floating-Point InstructionsSingle-Precision Operations Alpha finite number DefinitionsNon-finite number DenormalDirty zero InfinityMeaning Finite EncodingsTrue zero Sign Exponent Fraction VaxRounding Modes VAX Rounding ModesIeee Rounding Modes VAX-Format Arithmetic with Precise Exceptions VAX Rounding Mode Instruction NotationIeee Rounding Mode Instruction Notation Computational ModelsHigh-Performance VAX-Format Arithmetic IEEE-Compliant ArithmeticIEEE-Compliant Arithmetic Without Inexact Exception Trapping Modes High-Performance IEEE-Format ArithmeticVAX Trapping Modes When /U or /V mode is specified Ieee Trapping Modes VAX Trapping Modes Summary Trap Mode Notation MeaningSUI Summary of Ieee Trapping Modes Trap Mode Notation MeaningSVI Arithmetic Trap CompletionTrap Shadow Length Rules Page Invalid Operation INV Arithmetic Trap Overflow OVF Arithmetic Trap Division by Zero DZE Arithmetic TrapInteger Overflow IOV Arithmetic Trap Ieee Floating-Point Trap Disable BitsUnderflow UNF Arithmetic Trap Inexact Result INE Arithmetic TrapIeee Denormal Control Bits Floating-Point Control Register FpcrFloating-Point Control Register Fpcr Format Ieee Rounding Mode SelectedPage Accessing the Fpcr Default Values of the Fpcr Saving and Restoring the FpcrSoftware Notes Floating-Point Instruction Function Field Floating-Point Instruction Function Field FormatContents Meaning for Opcodes 1616 FNC ITOFS/ITOFTSQRTS/SQRTT Unpredictable Conversion of NaN and Infinity Values Ieee StandardCopying NaN Values Generating 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 Ieee AddfAddg AddsMult MulfMulg MulsCopy 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 Cmpglt VAX Floating CompareCmpgeq CmpgleCmptlt Ieee Floating CompareCmpteq CmptleConvert 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 17 Miscellaneous Instructions Summary Mnemonic Operation Miscellaneous InstructionsArchitecture 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 18 VAX Compatibility Instructions Summary Mnemonic Operation VAX Compatibility InstructionsVAX Compatibility Instructions Mnemonic Operation Multimedia Graphics and Video SupportByte and Word Minimum and Maximum Instruction mnemonics Pixel Error Pack Bytes Unpack Bytes Physical Address Space Characteristics Coherency of Memory AccessIntroduction Software/Hardware Note Granularity of Memory AccessMemory-Like and Non-Memory-Like Behavior Width of Memory AccessTranslation Buffers and Virtual Caches Caches and Write BuffersHardware/Software Coordination Note Page Atomic Update of a Single Datum Data SharingAtomic Change of a Single Datum STQ Atomic Update of Data Structures8Alpha Architecture Handbook Ordering Considerations for Shared Data Structures Alpha Shared Memory Model Read/Write OrderingImplementation Note Architectural Definition of Processor Issue Sequence Definition of Processor Issue ConstraintsDefinition of Before and After 1st↓ 2nd → PiIn=4y,b PiRny,b PiWny,b PiMB PiIMB Processor Issue ConstraintsDefinition of Location Access Constraints Definition of VisibilityDefinition of Storage Definition of Dependence Constraint Definition of Load-Locked and Store-Conditional PiPj Litmus TestsTimeliness Litmus Test 1 Impossible SequenceLitmus Test 3 Impossible Sequence Litmus Test 2 Impossible SequenceLitmus Test 4 Sequence Okay Litmus Test 5 Sequence OkayLitmus Test 6 Sequence Okay Litmus Test 8 Impossible Sequence Litmus Test 7 Impossible SequenceLitmus Test 9 Impossible Sequence Litmus Test 10 Sequence OkayLitmus Test 11 Impossible Sequence Single Processor Instruction Stream Implied BarriersImplications for Software Single Processor Data StreamSee Footnote 1 on First Processor Second Processor Multiprocessor Context SwitchPage Multiprocessor Send/Receive Interrupt Implications for Memory Mapped I/O Multiple Processors Writing to a Single I/O Device Implications for Hardware Dictable Arithmetic TrapsPALcode Instructions and Functions PALcodeSpecial Functions Required for PALcode PALcode EnvironmentPALcode Effects on System Code PALcode ReplacementPALcode Instructions that Require Recognition Mnemonic Name Required PALcode InstructionsIMB Required PALcode Instructions Mnemonic Type OperationDraina HaltCallpal Draina Drain AbortsCallpal Halt HaltCallpal IMB Instruction Memory BarrierConsole Subsystem Overview Page Input/Output Overview Page Unprivileged OpenVMS Alpha PALcode OpenVMS AlphaChmu ChmeChmk ChmsInsqhiqr InsqhilInsqhilr InsqhiqInsquel InsqtilrInsqtiq InsqtiqrRemqhil RdpsReadunq REIRemqtiq RemqhiqrRemqtil RemqtilrSwasten RemquelRemqueq RsccMfpr Privileged OpenVMS Alpha PalcodeCflush LdqpStqp SwpctxWtint Page Mnemonic Operation and Description Unprivileged Digital Unix PALcodePrivileged Digital Unix PALcode 10-3 10-4Alpha Architecture Handbook Unprivileged Windows NT Alpha PALcode Instruction Summary Unprivileged Windows NT Alpha PALcodePrivileged Windows NT Alpha PALcode 11-3 11-4Alpha Architecture Handbook 11-5 Page Hardware-Software Compact Appendix aInstruction-Stream Considerations Instruction AlignmentBranch Prediction and Minimizing Branch-Taken Factor Figure A-1 Branch-Format BSR and BR Opcodes Data Alignment Factor Data-Stream ConsiderationsImproving I-Stream Density Factor Instruction Scheduling FactorShared Data in Multiple Processors Factor Avoiding Cache/TB Conflicts Factor Figure A-3 Bad Allocation in Cache Prefetching Factor Sequential Read/Write FactorCode Sequences Aligned Byte/Word Within Register Memory AccessesDivision Byte Swap Stylized Code Forms4.1 NOP Load Literal Clear a RegisterBooleans Register-to-Register MoveNegate 4.6 notPseudo-Operations Stylized Code Forms Exceptions and Trap BarriersSoftware Considerations A-15 Timing Considerations Atomic Sequences Alpha Choices for Ieee Options Appendix B2Alpha Architecture Handbook Alpha Support for OS Completion Handlers Figure B-1 Ieee Floating-Point Control FPC Quadword Ieee Floating-Point Control FPC QuadwordPage Mapping to Ieee Standard Figure B-2 Ieee Trap Handling Behavior Table B-2 Ieee Floating-Point Trap Handling User Hardware1 Completion Signal Alpha Instructions Code HandlerMULx Output Exceptions Cmptlt Cmptle Input Exceptions CVTff Output ExceptionsSQRTx Output Exceptions Inexact Division by ZeroOverflow UnderflowCommon Architecture Instruction Summary Appendix CTable C-2 Common Architecture Instructions ADDL/VADDQ/V 15.0AF Convert Gfloating to quadword MULQ/V MULL/VSUBQ/V SUBL/VTable C-3 Ieee Floating-Point Instruction Function Codes Ieee Floating-Point InstructionsProgramming Note VAX Floating-Point InstructionsOpcode Summary Independent Floating-Point InstructionsTable C-6 Opcode Summary Table C-7 Key to Opcode Summary Symbol MeaningTable C-8 Common Architecture Opcodes in Numerical Order Common Architecture Opcodes in Numerical OrderInstruction Summary C-11 Addt Instruction Summary C-13 OpenVMS Alpha PALcode Instruction Summary Mfpripl MfprasnMfpresp MfprfenDigital Unix PALcode Instruction Summary Table C-12 Digital Unix Privileged PALcode InstructionsMnemonic Opcode Description Table C-14 Windows NT Alpha Privileged PALcode instructions Windows NT Alpha Instruction SummaryOpenVMS Alpha PALcode Opcodes in Numerical OrderTable C-15 PALcode Opcodes in Numerical Order Windows NTWtint 00.003F 00.0063 Table C-17 Opcodes Reserved for PALcode Mnemonic Required PALcode OpcodesOpcodes Reserved to PALcode Table C-16 Required PALcode Opcodes Mnemonic TypeOPC01 OPC02 OPC03 OPC04 OPC05 OPC06 OPC07 Opcodes Reserved to CompaqUnused Function Code Behavior Table C-18 Opcodes Reserved for Compaq MnemonicTable C-19 Ascii Character Set Hex Code Ascii Character SetEV3 Appendix DProcessor Type Assignments Table D-1 Processor Type Assignments Major Type Minor TypePALcode Variation Assignments Digital Unix Architecture Mask and Implementation ValuesTable D-3 Amask Bit Assignments Bit Meaning Table D-4 Implver Value Assignments MeaningPage Waivers Appendix EDECchip 21264 LDxL/STxC with WH64 Violation DECchip 21064/21066/21068 Performance Monitoring Implementation-Specific FunctionalityFor the OpenVMS Alpha Operating System Functions and Arguments for the DECchip 21064/21066/21068 Disable performance monitoring= PCMUX1 Select desired events muxctlSelect performance monitoring options = PCMUX0Value Description PC1 PC0Performance Monitor Interrupt Mechanism DECchip 21164/21164PC Performance MonitoringWindows NT Alpha Functions and Argument Input Contents Register Bits MeaningCTR0 CTR1PCSEL0 PCSEL2 OpenVMS Alpha and Digital Unix Functions and ArgumentsModeselect PCSEL1Select desired events Muxselect Disable performance monitoring do not reset countersRead the counters Select interrupt frequenciesOperate on counter MBZ PCSEL0 MBZMBZ PCSEL1 Counters Operate Under These Modes When Bits Set Bits MeaningS U P 6310 Table E-13 21164/21164PC Counter 1 PCSEL1 Event Selection Table E-14 21164/21164PC Counter 2 PCSEL2 Event Selection Table E-15 21164 CBOX1 Event Selection Value MeaningTable E-16 21164 CBOX2 Event Selection Table E-18 21164PC PM1MUX Event Selection Table E-17 21164PC PM0MUX Event Selection3 21264 Performance Monitoring PCTR1 SEXTPCTR0CTL47PCTR0 IERCMPCEN0Bit value Meaning SL1Select 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